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
Table of Contents
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 Complexity | Space Complexity | |
C++ | O(n2 * m) | O(n2) |
Java | O(n2 * m) | O(n2) |
JavaScript | O(n2 * m) | O(n2) |
Python | O(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 substringO(m)
. - The
O(n2)
space complexity is due to memoization and the recursion stack. - The memoization significantly reduces the exponential time complexity
O(2
n)
of naive backtracking to a polynomial time complexity.