6._单词拆分

$$dp[j] \text{ is true} \quad \text{AND} \quad \text{s.substring}(j, i) \text{ in wordDict}$$

• 2.18

  • 需要先确定 i，再确定 j，然后判断 0 到 j 是否存在，j 到 i 是否存在

• 2.4

  • 为了判断整个字符串 s 能否被拆分，我们把它拆解成：“能不能找到一个分割点 j，使得前半部分 s[0..j] 能被拆分，且后半部分 s[j..i] 恰好在字典里？”
  • 切割的是目标字符串，而不是单词表的字符串，j 代表落脚点，i 代表右边界

• 12.4

  • 笔记丢了,这是又补的
  1. 将LIst转换为set,方便查找复杂度为O1
  2. 0-j-i
  3. j不能等于i,不然取子串(i,i)为空,没意义
  4. 找到一个dp为true后直接跳出循环,找下一个i

class Solution {
    public boolean wordBreak(String s, List<String> wordDict) {
        Set<String> set = new HashSet<>(wordDict);
        boolean[] dp = new boolean[s.length()+1];
        dp[0] = true;
        for(int i=0;i<s.length()+1;i++){
            for(int j=0;j<i;j++){
                if(dp[j]&&set.contains(s.substring(j,i))){
                    dp[i]=true;
                    break;
                }
            }
        }
        return dp[s.length()];
    }
}