LeetCode Top 100 Liked Questions 139. Word Break (Java版； Medium)

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

class Solution {
    public boolean wordBreak(String s, List<String> wordDict) {
        int n = s.length();
        if(n==0){
            return true;
        }
        /*
        dp[i]表示前i个字符能否成功拆分
        dp[i] = dp[i-1]&& s[i-1] in dic || dp[i-2]&&s[i-2, i-1] in dic || ... || dp[0]&&s[0, i-1] in dic
        */
        boolean[] dp = new boolean[n+1];
        dp[0] = true;
        for(int i=1; i<=n; i++){
            for(int j=0; j<i; j++){
                if(dp[j] && wordDict.contains(s.substring(j, i))){
                    dp[i] = true;
                    break;
                }
            }
        }
        return dp[n];
    }
}

/*
动态规划版
*/
import java.util.Set;
import java.util.HashSet;

class Solution {
    public boolean wordBreak(String s, List<String> wordDict) {
        //构造函数的参数: HashSet(Collection<? extends E> c) 
        Set<String> set = new HashSet<String>(wordDict);
        //dp[j]表示以第s.charAt(j-1)结尾的子串分割后能否和字典中的单词匹配; 不存在s.charAt(-1), dp[0]初始化为true, 这个需要结合dp[j]的意义进行理解
        //dp[1]表示以s.charAt(0)为结尾的子串是否满足题意
        //dp[s.length()]表示以s.charAt(s.length()-1)为结尾的子串是否满足题意
        boolean[] dp = new boolean[s.length()+1];
        //初始化
        dp[0] = true;
        //以s.charAt(j)为结尾的各个子串
        for(int j=1; j<=s.length(); j++){
            //以s.charAt(i)为结尾的各个子串
            for(int i=0; i<j; i++){
                //注意&&后面的是dp[i]不是dp[j], 要理解动态规划的思路
                if(set.contains(s.substring(i,j)) && dp[i]){
                    dp[j] = true;
                    break;
                }
            }
        }
        return dp[s.length()];
    }
}

时间复杂度：O(n^2), 回溯树的大小最多达到 n^2. 这么理解吧, 经过剪枝后, 对于s.charAt(start)来说,
能作为end的都有start+1,...,s.length(), 尝试一个end只需一次递归, 不再需要针对某一个end一直递归到尽头,
因为memo都已经记录好了每个memo[end]的结果, 这里需要配合理解Boolean[]中各个值是自底向上填充的

空间复杂度：O(n), 回溯树的深度可以达到 n 级别。

/*
来一个暴力递归版, 剪枝版回溯法
首先得弄清楚重复子问题来自哪里? 
比如:s=aaaaab; dict=a,aa,aaa,aaaa,aaaaa
递归调用过程:
a; a; a; a; a; b (1)
a; a; a; a; ab
a; a; a; aa; b
a; a; a; aab
...
aa; a; a; a; b (2)
aa; a; a; ab
aa; a; aa; b
aa; a; aab
只看(1)和(2)就可以发现后4个a;a;a;b重复出现了, 可以使用memo数组, 记录以s.charAt(2)为首字母的子串能够匹配s.substring(2)! 之后再次以2为起点进行判断时便不用递归了, 直接查询memo[2]即可

绊脚案例:
"catsandog"   ["cats","dog","sand","and","cat"]   false
*/
class Solution {
    public boolean wordBreak(String s, List<String> wordDict) {
        //no input check needed according to the problem
        //HashSet(Collection<? extends E> c) 
        HashSet set = new HashSet(wordDict);
        //用于剪枝的memo数组, memo[i]表示以s.charAt(i)为开头
        //为什么用Boolean而不是boolean, 为了使用null; null表示没有memo[i]没有记录, 需要进行处理
        Boolean[] memo = new Boolean[s.length()];
        return Core(s, set, 0, memo);
    }
    /*
    递归逻辑:判断以s.charAt(start)为首字母的子串中,是否有能够匹配wordDict中某个单词的子串, 有的话继续以s.charAt(end)为首字母(新条件新递归)进行判断, 没有的继续遍历下一个可能的子串
    自底向上
    */
    public boolean Core(String s, HashSet<String> set, int start, Boolean[] memo){
        //base case
        if(start==s.length())
            return true;
        if(memo[start]!=null)
            return memo[start];
        //以s.charAt(end-1)为末尾字符, 遍历各个可能的子串
        //使用memo剪枝的话, 需要自底向上判断; 因为自顶向下无法剪枝, 以start开头的情况在后面就用不到了,  说错了, 起始还是会用到的, 看最上面的手写案例
        for(int end = start + 1; end<=s.length(); end++){
            if(set.contains(s.substring(start, end)) && Core(s, set, end, memo)){
                memo[start] = true;
                return true;
            }
        }
        memo[start]=false;
        return false;
    }
}

复杂度分析

时间复杂度：O(n^n)  考虑最坏情况 s = aaaaaaa, 每一个前缀都在字典中，此时回溯树的复杂度会达到 n^
n
空间复杂度：O(n) 。回溯树的深度最深达到 n 。

"aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaab"
["a","aa","aaa","aaaa","aaaaa","aaaaaa","aaaaaaa","aaaaaaaa","aaaaaaaaa","aaaaaaaaaa"]

/*
来一个暴力递归版, 回溯法
*/
class Solution {
    public boolean wordBreak(String s, List<String> wordDict) {
        //no input check needed according to the problem
        //HashSet(Collection<? extends E> c) 
        HashSet set = new HashSet(wordDict);
        return Core(s, set, 0);
    }
    /*
    递归逻辑:挨个遍历以s.charAt(start)为首字母的子串(当前条件), 如果其中某个子串包含在set中, 则尝试以s.charAt(end)为首字母的所有子串(新条件新递归)
    自顶向下
    */
    public boolean Core(String s, Set<String> set, int start){
        //base case
        if(start==s.length())
            return true;
        //尝试以s.charAt(start)作为首字母的各种子串是否满足条件(暴力)
        //循环的起始条件和终止条件和str.substring()的用法密切相关
        for(int end=start+1; end<=s.length(); end++){
            //substring()是左闭右开
            String curr = s.substring(start, end);
            if(set.contains(curr) && Core(s, set, end))
                return true;
        }
        return false;
    }
}