Word Break

Given a non-empty string s and a dictionary wordDict containing a list of non-empty words, determine if s can be segmented into a space-separated sequence of one or more dictionary words.
Note:
The same word in the dictionary may be reused multiple times in the segmentation. You may assume the dictionary does not contain duplicate words.
Example 1:
Input: s = "leetcode", wordDict = ["leet", "code"]
Output: true
Explanation: Return true because "leetcode" can be segmented as "leet code".
Example 2:
Input: s = "applepenapple", wordDict = ["apple", "pen"]
Output: true
Explanation: Return true because "applepenapple" can be segmented as "apple pen apple".
Note that you are allowed to reuse a dictionary word.
Example 3:
Input: s = "catsandog", wordDict = ["cats", "dog", "sand", "and", "cat"]
Output: false

Analysis

不是一般的DP,在这类有 Word Dict的题目时,容易想到用Trie来存,但是并不一定能够带来算法效率的提升。
dp[i] 来表示从0到i, 即[0, 1),左闭右开区间,是否满足可以分解成的词都来自字典。
状态转移方程:dp[i] = dp[j] && wordDict.contains(s.substring(j, i))
起始条件:dp[0] = true;
答案:dp[s.length()]

Solution

DP - O(n) space, O(n^2) - (14ms, 18.91% AC)
class Solution {
public boolean wordBreak(String s, List<String> wordDict) {
/*
HashSet<String> wordSet = new HashSet<String>();
for (String word: wordDict) {
wordSet.add(word);
}
*/
Set<String> wordSet = new HashSet(wordDict);
boolean isWord[] = new boolean[s.length() + 1];
isWord[0] = true;
for (int i = 1; i < s.length() + 1; i++) {
for (int j = 0; j < i; j++) {
if (isWord[j] && wordSet.contains(s.substring(j, i))) {
isWord[i] = true;
break;
}
}
}
return isWord[s.length()];
}
}
DP - without converting list to set (7ms, 74.94% AC)
class Solution {
public boolean wordBreak(String s, List<String> wordDict) {
boolean[] dp = new boolean[s.length() + 1];
dp[0] = true;
for (int i = 1; i <= s.length(); i++) {
for (int j = i - 1; j >= 0; j--) {
dp[i] = dp[j] && wordDict.contains(s.substring(j, i));
if(dp[i]) break;
}
}
return dp[s.length()];
}
}
DP - Optimize with Max Length constraint (2ms, 100%)
class Solution {
private int getMaxLength(List<String> wordDict) {
int max = 0;
for (String word: wordDict) {
if (word.length() > max) {
max = word.length();
}
}
return max;
}
public boolean wordBreak(String s, List<String> wordDict) {
boolean[] dp = new boolean[s.length() + 1];
dp[0] = true;
int maxLen = getMaxLength(wordDict);
for (int i = 1; i <= s.length(); i++) {
for (int j = i - 1; j >= 0 && i - j <= maxLen; j--) {
dp[i] = dp[j] && wordDict.contains(s.substring(j, i));
if (dp[i]) {
break;
}
}
}
return dp[s.length()];
}
}
Another DP Solution
public class Solution {
public boolean wordBreak(String s, Set<String> dict) {
boolean[] f = new boolean[s.length() + 1];
f[0] = true;
for(int i = 1; i <= s.length(); i++){
for(String str: dict){
if(str.length() <= i){
if(f[i - str.length()]){
if(s.substring(i-str.length(), i).equals(str)){
f[i] = true;
break;
}
}
}
}
}
return f[s.length()];
}
}

Reference