Given a string s and a dictionary of strings wordDict, return true if s can be segmented into a space-separated sequence of one or more dictionary words.
Example 1
Input: s = "leetcode", wordDict = ["leet","code"]
Output: true
Explanation: "leet code"
Example 2
Input: s = "applepenapple", wordDict = ["apple","pen"]
Output: true
Explanation: "apple pen apple"
Example 3
Input: s = "catsandog", wordDict = ["cats","dog","sand","and","cat"]
Output: false
1 <= s.length <= 3001 <= wordDict.length <= 1000The brute-force recursive idea: at each position, try every possible next word from the dictionary and recurse — correct, but the same suffix of the string gets re-examined across many different branches.
dp[i] = true if s[0..i] can be segmented — built bottom-up so each prefix length is resolved exactly once, not recomputed per branch.
For each i, dp[i] is true if some earlier dp[j] is true AND s[j..i] is itself a dictionary word — trying every valid split point j.
public boolean wordBreakBruteForce(String s, List<String> wordDict) {
Set<String> dict = new HashSet<>(wordDict);
return helper(s, 0, dict);
}
private boolean helper(String s, int start, Set<String> dict) {
if (start == s.length()) return true;
for (int end = start + 1; end <= s.length(); end++) {
if (dict.contains(s.substring(start, end)) && helper(s, end, dict)) {
return true;
}
}
return false;
}Time: O(2^n) worst case · Space: O(n) recursion depth