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

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