Dare2Solve
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.
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.
Initialization: Convert the wordDict
list into a set for efficient lookup operations. Initialize a memoization dictionary to store results of subproblems.
Backtracking Function:
v
: The current word being formed.i
: The current index in the string s
.s
is reached, check if the remaining part of v
is empty. If so, return True
.v + 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.v
by adding the current character s[i]
and check the remaining substring.Memoization:
v
to store and retrieve results from the memoization dictionary.The worst-case time complexity is exponential due to the recursive exploration of all possible segmentations of the string. Memoization helps reduce redundant calculations.
O(n) for the memoization dictionary and the recursion call stack, where n
is the length of the string s
.
class Solution {
public:
bool wordBreak(string s, vector<string>& wordDict) {
unordered_set<string> dict(wordDict.begin(), wordDict.end());
unordered_map<string, bool> visited;
function<bool(string, int, string)> 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, "");
}
};
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()
class Solution {
public boolean wordBreak(String s, List<String> wordDict) {
Set<String> dict = new HashSet<>(wordDict);
Map<String, Boolean> visited = new HashMap<>();
return backtrack(s, dict, "", 0, visited);
}
private boolean backtrack(String s, Set<String> dict, String v, int i, Map<String, Boolean> 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;
}
}
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();
};