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 <= 1000dp[i] = true if s[0..i] can be segmented. dp[i] = true if dp[j] && s[j..i] is in dictionary.
public boolean wordBreak(String s, List<String> wordDict) {
Set<String> dict = new HashSet<>(wordDict);
boolean[] dp = new boolean[s.length() + 1];
dp[0] = true; // empty string is always segmentable
for (int i = 1; i <= s.length(); i++) {
for (int j = 0; j < i; j++) {
if (dp[j] && dict.contains(s.substring(j, i))) {
dp[i] = true;
break;
}
}
}
return dp[s.length()];
}Time: O(n³) for substring creation · Space: O(n)