Leetcode Word Break II problem solution

YASH PAL,

In this Leetcode Word Break II problem solution we have Given a string s and a dictionary of strings wordDict, add spaces in s to construct a sentence where each word is a valid dictionary word. Return all such possible sentences in any order.

Leetcode Word Break II problem solution

Problem solution in Python.

class Solution:
    def wordBreak(self, s: str, wordDict: List[str]) -> List[str]:
        res = []
        self.wordDict = set(wordDict)
        self.dfs(s, [], res)
        return res
    def dfs(self, s, path, res):
        if not s:
            res.append(" ".join(path))
            return
        
        for i in range(len(s)):
            if s[:i+1] in self.wordDict:
                self.dfs(s[i+1:], path+[s[:i+1]], res)

Problem solution in Java.

public List<String> wordBreak(String s, Set<String> wordDict) {
    return DFS(s, wordDict, new HashMap<String, LinkedList<String>>());
}       

List<String> DFS(String s, Set<String> wordDict, HashMap<String, LinkedList<String>>map) {
    if (map.containsKey(s)) 
        return map.get(s);
        
    LinkedList<String>res = new LinkedList<String>();     
    if (s.length() == 0) {
        res.add("");
        return res;
    }               
    for (String word : wordDict) {
        if (s.startsWith(word)) {
            List<String>sublist = DFS(s.substring(word.length()), wordDict, map);
            for (String sub : sublist) 
                res.add(word + (sub.isEmpty() ? "" : " ") + sub);               
        }
    }       
    map.put(s, res);
    return res;
}

Problem solution in C++.

class Solution 
{
public:
    void helper(string &s,string &curr,vector<string>&v,int index,unordered_set<string>&dict)
    {
        if(index==s.length())
        {
            curr.erase(curr.begin()+curr.length()-1);
            v.push_back(curr);
            return;
        }
        string tmp="";
        for(int i=index;i<s.length();i++)
        {
            tmp.push_back(s[i]);
            if(dict.find(tmp)!=dict.end())
            {
                string aux=curr;
                curr+=(tmp+" ");
                helper(s,curr,v,i+1,dict);
                curr=aux;
            }
        }
    }
    vector<string> wordBreak(string s, vector<string>& wordDict) 
    {
        unordered_set<string>dict(wordDict.begin(),wordDict.end());
        vector<string>v;
        string curr="";
        helper(s,curr,v,0,dict);
        return v;
    }
};

coding problems