# 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[i]` 来表示从0到i, 即`[0, 1)`，左闭右开区间，是否满足可以分解成的词都来自字典。

## 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) {
}
*/
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

https://leetcode.com/problems/word-break/discuss/43886/Evolve-from-brute-force-to-optimal-a-review-of-all-solutions

https://leetcode.com/problems/word-break/discuss/43790/Java-implementation-using-DP-in-two-ways

Last updated