Problem
You are given a strings and a list of strings wordDict.
Return
true if s can be segmented into one or more words from wordDict. Otherwise, return false.
A word from the dictionary can be used multiple times.
Example(s)
Consider the following example(s) to understand the expected input and output.Input
s = "applepenapple" wordDict = ["apple", "pen"] Output
true"apple" + "pen" + "apple"Memoization Approach
To determine whether the string can be segmented, we start from an index and try every word from the dictionary.If a dictionary word matches the substring starting at the current index, we move forward by the length of that word and recursively check whether the remaining part of the string can also be segmented.
If we reach the end of the string, the entire string has been successfully segmented, so we return
true.
The same index can be reached through different combinations of words, so we store the result for each index using memoization.
class Solution {
public boolean wordBreak(String s, List<String> wordDict) {
Boolean[] memo = new Boolean[s.length()];
return canBreak(s, 0, wordDict, memo);
}
private boolean canBreak(String s, int index, List<String> wordDict, Boolean[] memo) {
// Successfully segmented the entire string.
if (index == s.length()) {
return true;
}
// Return the cached result.
if (memo[index] != null) {
return memo[index];
}
// Try every word from the dictionary.
for (String word : wordDict) {
int length = word.length();
if (index + length <= s.length() && s.startsWith(word, index) && canBreak(s, index + length, wordDict, memo)) {
return memo[index] = true;
}
}
return memo[index] = false;
}
}
Complexity
There aren possible starting indices, and each index is calculated only once.
For each index, we may check every word in the dictionary and compare its characters with the string, resulting in
O(n × m × k) time complexity, where m is the number of words and k is the maximum word length. The memoization array requires O(n) space.
Tabulation Approach
We can also solve the problem using bottom-up Dynamic Programming.Let
dp[i] represent whether the substring from index 0 to i - 1 can be segmented using words from the dictionary.
An empty string can always be segmented, so
dp[0] is true.
For every position
i, we check every word in the dictionary. If the substring ending at i matches a dictionary word and the part before that word can also be segmented, then dp[i] is true.
class Solution {
public boolean wordBreak(String s, List<String> wordDict) {
int n = s.length();
boolean[] dp = new boolean[n + 1];
// An empty string can be segmented.
dp[0] = true;
for (int i = 1; i <= n; i++) {
for (String word : wordDict) {
int length = word.length();
if (i >= length && dp[i - length] && s.startsWith(word, i - length)) {
dp[i] = true;
break;
}
}
}
return dp[n];
}
}
Complexity
There aren positions, and for each position we may check every word in the dictionary and compare its characters with the string, resulting in O(n × m × k) time complexity, where m is the number of words and k is the maximum word length.
The DP array requires
O(n) space.