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 wordBreak(String s, List wordDict) {
List result = new ArrayList<>();
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 List wordBreak(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 IList WordBreak(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);
                }
            }
        }
    }
}