Solution For Word Break Ii
Problem Statement:
Given a non-empty string s and a dictionary wordDict containing a list of non-empty words, add spaces in s to construct a sentence where each word is a valid dictionary word. Return all such possible sentences.
Note:
The same word in the dictionary may be reused multiple times in the segmentation.
You may assume the dictionary does not contain duplicate words.
Example 1:
Input:
s = “catsanddog”
wordDict = [“cat”, “cats”, “and”, “sand”, “dog”]
Output:
[
“cats and dog”,
“cat sand dog”
]
Example 2:
Input:
s = “pineapplepenapple”
wordDict = [“apple”, “pen”, “applepen”, “pine”, “pineapple”]
Output:
[
“pine apple pen apple”,
“pineapple pen apple”,
“pine applepen apple”
]
Explanation: Note that you are allowed to reuse a dictionary word.
Solution:
The problem can be solved using a recursive approach. We start iterating over the input string and keep on adding characters to the currentWord until we find a match in the word dictionary. As soon as we find a match, we add the currentWord to the result and start with the next character. We keep on doing this until we reach the end of the string. However, this approach can get very slow if the input string is very large, or if multiple valid sentences can be formed.
To optimize this approach, we will use dynamic programming. We store a boolean array of size n+1, where n is the length of the input string. dp[i] represents whether the string upto the i-th index can be segmented into words from the dictionary or not. We also store a hashmap of size n+1, where the key represents the index upto which we have already found valid solutions, and the value is a list of possible sentences.
We start by initializing dp[0] to be true, since an empty string is always a valid solution. Then we iterate over the string s and check if s[j:i] (where j is any index upto i) is a valid word from the dictionary, and if dp[j] is also true (meaning the string upto index j can be segmented into words). If both these conditions are met, we set dp[i] to be true and add the substring s[j:i] to the list of possible sentences at index i in the hashmap.
Finally, we recursively traverse the hashmap, starting from the last index, and build the valid sentences.
Here’s the complete code:
class Solution {
public List
List
int n = s.length();
// Create a hashmap to store possible sentences upto each index
HashMap<Integer, List<String>> memo = new HashMap<>();
memo.put(n, new ArrayList<>());
memo.get(n).add("");
// Create a boolean array to store whether the string upto an index can be segmented into words or not
boolean[] dp = new boolean[n+1];
dp[n] = true;
// Populate the boolean array and hashmap
for(int i=n-1; i>=0; i--) {
List<String> list = new ArrayList<>();
for(int j=i+1; j<=n; j++) {
if(dp[j] && wordDict.contains(s.substring(i,j))) {
dp[i] = true;
if(memo.containsKey(j)) {
for(String str: memo.get(j)) {
list.add(s.substring(i,j) + (str.equals("") ? "" : " ") + str);
}
}
}
}
memo.put(i, list);
}
// Build valid sentences using hashmap
return memo.get(0);
}
}
Time Complexity: O(n^2 * wordDict.length), where n is the length of the input string. We iterate over each index in the string n times, and for each index, we iterate over all possible substrings. We also need to check whether a string is present in the word dictionary, which takes O(wordDict.length) time.
Space Complexity: O(n^2), for the hashmap and boolean array.
Step by Step Implementation For Word Break Ii
public class Solution { public ListwordBreak(String s, Set wordDict) { List result = new ArrayList (); List list = new ArrayList (); wordBreakHelper(s, wordDict, result, list); return result; } public void wordBreakHelper(String s, Set wordDict, List result, List list){ if(s.length() == 0){ StringBuilder sb = new StringBuilder(); for(String str : list){ sb.append(str); sb.append(" "); } sb.deleteCharAt(sb.length()-1); result.add(sb.toString()); return; } for(int i = 1; i <= s.length(); i++){ String str = s.substring(0,i); if(wordDict.contains(str)){ list.add(str); wordBreakHelper(s.substring(i), wordDict, result, list); list.remove(list.size()-1); } } } }
class Solution: # @param s: A string # @param wordDict: A set of words. # @return: All possible sentences. def wordBreak(self, s, wordDict): # write your code here def dfs(s, wordDict, stringlist): if self.check(s, wordDict): if len(s) == 0: results.append(stringlist[1:]) for i in range(1, len(s)+1): if s[:i] in wordDict: dfs(s[i:], wordDict, stringlist+[s[:i]]) results = [] dfs(s, wordDict, []) return results def check(self, s, wordDict): dp = [False for i in range(len(s)+1)] dp[0] = True for i in range(1, len(s)+1): for k in range(i): if dp[k] and s[k:i] in wordDict: dp[i] = True return dp[len(s)]
var wordBreak = function(s, wordDict) { // create a map to store all the possible word breaks // for a string (from the dictionary) let map = new Map(); // create a set to store all the dictionary words let set = new Set(wordDict); // helper function to check if a string can be broken into // dictionary words let canBreak = function(str) { // if the string is empty, then it can be broken if (str.length === 0) { return true; } // if we have already calculated the result for this string, // then return the result from the map if (map.has(str)) { return map.get(str); } // iterate through the string for (let i = 1; i <= str.length; i++) { // get the substring from the start of the string to the current index let prefix = str.substring(0, i); // if the prefix is in the dictionary, then we can check if the // remaining string can also be broken into dictionary words if (set.has(prefix) && canBreak(str.substring(i))) { // store the result in the map and return true map.set(str, true); return true; } } // if we reach here, then it means that the string cannot be broken // into dictionary words, so we store false in the map and return false map.set(str, false); return false; } // check if the input string can be broken into dictionary words if (!canBreak(s)) { return []; } // helper function to get all the possible word breaks for a string let getBreaks = function(str) { // if the string is empty, then return an empty array if (str.length === 0) { return []; } // if we have already calculated the result for this string, // then return the result from the map if (map.has(str)) { return map.get(str); } // result array let result = []; // iterate through the string for (let i = 1; i <= str.length; i++) { // get the substring from the start of the string to the current index let prefix = str.substring(0, i); // if the prefix is in the dictionary, then we can check if the // remaining string can also be broken into dictionary words if (set.has(prefix)) { // if the remaining string can be broken into dictionary words, // then get all the possible word breaks for the remaining string let suffixBreaks = getBreaks(str.substring(i)); // iterate through all the possible word breaks for the remaining string for (let j = 0; j < suffixBreaks.length; j++) { // add the prefix to the word break and add it to the result array result.push(prefix + ' ' + suffixBreaks[j]); } } } // store the result in the map and return it map.set(str, result); return result; } // return all the possible word breaks for the input string return getBreaks(s); };
class Solution { public: // backtracking function to find all possible strings that can be formed void findAllPossibleWords(string s, int index, unordered_set& wordDict, string& currentString, vector & allPossibleWords) { // if we have reached the end of the string if(index == s.length()) { // add the current string to the list of all possible words allPossibleWords.push_back(currentString); // return from the function return; } // iterate over all the remaining characters in the string for(int i = index; i < s.length(); i++) { // extract the substring from the current index to the current index + i string substring = s.substr(index, i - index + 1); // if the substring is present in the word dictionary if(wordDict.find(substring) != wordDict.end()) { // add the substring to the current string currentString += substring + " "; // call the backtracking function recursively for the remaining part of the string findAllPossibleWords(s, i + 1, wordDict, currentString, allPossibleWords); // remove the substring from the current string currentString.erase(currentString.length() - substring.length() - 1); } } } vector wordBreak(string s, vector & wordDict) { // create a set from the given word dictionary for faster lookup unordered_set wordSet(wordDict.begin(), wordDict.end()); // create an empty vector to store all the possible words that can be formed vector allPossibleWords; // create an empty string to store the current word string currentString = ""; // call the backtracking function to find all possible words findAllPossibleWords(s, 0, wordSet, currentString, allPossibleWords); // return the vector of all possible words return allPossibleWords; } };
using System; using System.Collections.Generic; public class Solution { public IListWordBreak(string s, IList wordDict) { // create a list to store all the possible sentences IList result = new List (); // create a set to store all the words in the dictionary HashSet set = new HashSet (wordDict); // create a two-dimensional array to store all the possible substrings // that can be formed from the given string bool[,] dp = new bool[s.Length, s.Length]; // fill up the dp array for(int i = 0; i < s.Length; i++) { for(int j = i; j < s.Length; j++) { string substring = s.Substring(i, j - i + 1); // if the substring is in the set, then it is a valid word // and we can set the dp value to true if(set.Contains(substring)) { dp[i, j] = true; } // if the substring is not in the set, then check if it can be // formed by concatenating two valid words else { for(int k = i; k < j; k++) { if(dp[i, k] && dp[k + 1, j]) { dp[i, j] = true; break; } } } } } // now that we have the dp array filled up, we can use it to generate // all the possible sentences GenerateSentences(s, dp, 0, new List (), result); return result; } // this function generates all the possible sentences by making use of the dp array public void GenerateSentences(string s, bool[,] dp, int index, List current, IList result) { // if we have reached the end of the string, then we have generated a sentence if(index == s.Length) { // convert the list of words into a string and add it to the result result.Add(String.Join(" ", current)); } // if we have not reached the end of the string, then keep generating sentences else { for(int i = index; i < s.Length; i++) { // if the substring from index to i can be formed by concatenating // valid words, then we can add it to the current sentence if(dp[index, i]) { string substring = s.Substring(index, i - index + 1); current.Add(substring); // generate all the possible sentences by making use of the dp array GenerateSentences(s, dp, i + 1, current, result); // remove the word from the current sentence current.RemoveAt(current.Count - 1); } } } } }