🎨Now live: Try our Free AI Image Generation Feature

Description
The wordBreak
function determines if a string s
can be segmented into one or more words from a given dictionary wordDict
. The dictionary contains a list of valid words.
Intuition
To solve the problem, we need to check if the string s
can be divided into a sequence of words that all exist in the dictionary. We use a backtracking approach combined with memoization to efficiently explore and remember previously computed results.
Approach
- Initialization: Convert the
wordDict
list into a set for efficient lookup operations. Initialize a memoization dictionary to store results of subproblems. - Backtracking Function:
- Parameters:
-
v
: The current word being formed. -i
: The current index in the strings
. - Base Case: If the end of the strings
is reached, check if the remaining part ofv
is empty. If so, returnTrue
. - Recursive Case: - Ifv + s[i]
forms a valid word in the dictionary, recursively check if the rest of the string starting from the next index can also be segmented. - If not, continue to buildv
by adding the current characters[i]
and check the remaining substring. - Memoization:
- Cache results of previously computed subproblems to avoid redundant computations.
- Use a key derived from the current index and the length of the current word
v
to store and retrieve results from the memoization dictionary.
Complexity
Time Complexity:
The worst-case time complexity is exponential due to the recursive exploration of all possible segmentations of the string. Memoization helps reduce redundant calculations.
Space Complexity:
O(n) for the memoization dictionary and the recursion call stack, where n
is the length of the string s
.
Code
C++
class Solution {
public:
bool wordBreak(string s, vector& wordDict) {
unordered_set dict(wordDict.begin(), wordDict.end());
unordered_map visited;
function backtrack = [&](string v, int i, string visitedKey) -> bool {
if (i == s.size()) return v.empty();
visitedKey = to_string(i - v.size()) + "_" + to_string(i);
if (visited.find(visitedKey) != visited.end()) return visited[visitedKey];
bool res = false;
if (dict.find(v + s[i]) != dict.end()) res = backtrack("", i + 1, visitedKey);
if (!res) res = backtrack(v + s[i], i + 1, visitedKey);
visited[visitedKey] = res;
return res;
};
return backtrack("", 0, "");
}
};
Python
class Solution:
def wordBreak(self, s: str, wordDict: List[str]) -> bool:
dict_set = set(wordDict)
visited = {}
def backtrack(v="", i=0):
if i == len(s):
return v == ""
visited_key = f"{i - len(v)}_{i}"
if visited_key in visited:
return visited[visited_key]
res = False
if v + s[i] in dict_set:
res = backtrack("", i + 1)
if not res:
res = backtrack(v + s[i], i + 1)
visited[visited_key] = res
return res
return backtrack()
Java
class Solution {
public boolean wordBreak(String s, List wordDict) {
Set dict = new HashSet<>(wordDict);
Map visited = new HashMap<>();
return backtrack(s, dict, "", 0, visited);
}
private boolean backtrack(String s, Set dict, String v, int i, Map visited) {
if (i == s.length()) return v.isEmpty();
String visitedKey = (i - v.length()) + "_" + i;
if (visited.containsKey(visitedKey)) return visited.get(visitedKey);
boolean res = false;
if (dict.contains(v + s.charAt(i))) res = backtrack(s, dict, "", i + 1, visited);
if (!res) res = backtrack(s, dict, v + s.charAt(i), i + 1, visited);
visited.put(visitedKey, res);
return res;
}
}
JavaScript
var wordBreak = function(s, wordDict) {
const dict = new Set(wordDict);
const backtrack = (v="",i=0, visited = new Map())=>{
if(i==s.length) return v=="";
if(visited.has((i-v.length)+"_"+i)) return visited.get((i-v.length)+"_"+i);
let res = false;
if(dict.has(v+s[i])) res = backtrack("",i+1,visited);
if(!res) res = backtrack(v+s[i],i+1,visited);
visited.set((i-v.length)+"_"+i, res);
return res;
}
return backtrack();
};