Word Break II LeetCode Solution

Last updated on January 14th, 2025 at 06:30 am

Here, we see a Word Break II LeetCode Solution. This Leetcode problem is solved using different approaches in many programming languages, such as C++, Java, JavaScript, Python, etc.

List of all LeetCode Solution

Topics

Backtracking, Dynamic Programming

Companies

Dropbox, Google, Snapchat, Twitter, Uber

Level of Question

Hard

Word Break II LeetCode Solution

Word Break II LeetCode Solution

1. 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: []

2. Coding Pattern Used in Solution

The coding pattern used in all the provided implementations is “Backtracking with Memoization”. This pattern involves exploring all possible solutions recursively (backtracking) while storing intermediate results (memoization) to avoid redundant computations. This is a common approach for solving problems like word segmentation, where the solution space can be large, but overlapping subproblems can be reused.

3. Code Implementation in Different Languages

3.1 Word Break II 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];
        }
};

3.2 Word Break II 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.3 Word Break II 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);
};

3.4 Word Break II 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

4. Time and Space Complexity

Time ComplexitySpace Complexity
C++O(n2 * m)O(n2)
JavaO(n2 * m)O(n2)
JavaScriptO(n2 * m)O(n2)
PythonO(n2 * m)O(n2)

where n be the length of the string and m be the size of the dictionary.

  • The O(n2 * m) time complexity arises because of the recursive exploration of substrings O(n2) and the dictionary lookup for each substring O(m).
  • The O(n2) space complexity is due to memoization and the recursion stack.
  • The memoization significantly reduces the exponential time complexity O(2n) of naive backtracking to a polynomial time complexity.
Scroll to Top