Last updated on July 20th, 2024 at 04:08 am

Here, We see Word Break II LeetCode Solution. This Leetcode problem is done in many programming languages like C++, Java, JavaScript, Python, etc. with different approaches.

List of all LeetCode Solution

Topics

Backtracking, Dynamic Programming

Companies

Dropbox, Google, Snapchat, Twitter, Uber

Level of Question

Hard

Word Break II LeetCode Solution

Problem Statement

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.

Note that the same word in the dictionary may be reused multiple times in the segmentation.

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.

Example 3:
Input: s = “catsandog”, wordDict = [“cats”,”dog”,”sand”,”and”,”cat”]
Output: []

1. Word Break II LeetCode Solution C++

class Solution {
    public:
        vector<string> wordBreak(string s, vector<string>& wordDict) 
        {
            int max_len = 0;
            unordered_set<string> dict;
            for(string& str : wordDict)
            {
                dict.insert(str);
                max_len = max(max_len, (int)str.length());
            }
            unordered_map<int, vector<string>> mp;
            return break_word(s, 0, dict, max_len, mp);
        }

    protected:
        vector<string> break_word(  const string& s, int n, unordered_set<string>& dict, 
                                    int max_len, unordered_map<int, vector<string>>& mp)
        {
            if(mp.count(n)) return mp[n];
            string str;
            for(int i = n; i < s.length() && str.length() <= max_len; ++i)
            {
                str += s[i];
                if(dict.count(str))
                {
                    if(i == s.length()-1)
                        mp[n].push_back(str);
                    else
                    {
                        vector<string> vs = break_word(s, i+1, dict, max_len, mp);
                        for(auto& a : vs) mp[n].push_back(str + " " + a);
                    }
                }
            }
            return mp[n];
        }
};

2. Word Break II LeetCode Solution Java

class Solution {
    private void helper(String s, int i, Set<String> dict, List<String> cur, List<String> res) {
        if (i == s.length()) {
            if (cur.size() > 0) {
                StringBuilder sb = new StringBuilder();
                for (int j = 0; j < cur.size(); j++) {
                    if (j > 0) {
                        sb.append(' ');
                    }
                    sb.append(cur.get(j));
                }
                res.add(sb.toString());
            }
            return;
        }
        for (int j = i+1; j <= s.length(); j++) {
            if (dict.contains(s.substring(i, j))) {
                cur.add(s.substring(i, j));
                helper(s, j, dict, cur, res);
                cur.remove(cur.size() - 1);
            }
        }
    }
    public List<String> wordBreak(String s, List<String> wordDict) {
        Set<String> dict = new HashSet<>(wordDict);
        List<String> res = new ArrayList<>();
        List<String> cur = new ArrayList<>();
        helper(s, 0, dict, cur, res);
        return res;
    }
}

3. Word Break II Solution JavaScript

var wordBreak = function(s, wordDict) {
    const memo = new Map();
    function run(str) {
        if(memo.has(str)) return memo.get(str);
        if(!str.length) return [];
        const result = [];
        for(let word of wordDict) {
            if(str.startsWith(word)) {
                const next = str.slice(word.length);
                const paths = run(next); 
                if(!paths.length && !next.length) result.push(word);
                result.push(...paths.map(rest => word + ' ' + rest));
            }
        }
        memo.set(str, result);
        return result;
    }
    return run(s);
};

4. Word Break II Solution Python

class Solution(object):
    def wordBreak(self, s, wordDict):
        return self.helper(s, wordDict, {})
    def helper(self, s, wordDict, memo):
        if s in memo: return memo[s]
        if not s: return []
        res = []
        for word in wordDict:
            if not s.startswith(word):
                continue
            if len(word) == len(s):
                res.append(word)
            else:
                resultOfTheRest = self.helper(s[len(word):], wordDict, memo)
                for item in resultOfTheRest:
                    item = word + ' ' + item
                    res.append(item)
        memo[s] = res
        return res