139. 单词拆分 (opens new window)

1.DFS+剪枝

解题思路：DFS搜索每个前缀字符串是否能够被模式串匹配。需要注意如果不剪枝的话搜索空过大，从而导致超时，因此需要剪枝。

首先明白什么情况下需要剪枝，假设当前需要匹配的字符串为“aabbccc”，而模式串为["aa","bb","aabb"]，当前字符串dfs搜索发现aabb子串可以进行匹配，但是这里有两种方式，如果不进行剪枝的话使用“aa” "bb"匹配和使用"aabb"两种匹配方式都会被搜索到，而题目最终只需要判断字符串能否匹配，并需要给出所有匹配的方案数。因此对于从开始索引0到当前索引下标i的子串，在搜索时需要保证它只会被匹配一次。

剪枝：做法是开辟一个list容器空间，保存已经匹配的子串下标i。每次搜索当前位置时，除了需要判断以当前索引结尾的子串是否可以匹配之外，还需要判断当前位置是否被匹配过。

class Solution {
    public boolean wordBreak(String s, List<String> wordDict) {
        List<Integer> list=new ArrayList<>();
        return dfs(s,wordDict,list,0);
    }
    public boolean dfs(String s,List<String> wordDict,List<Integer> list,int index){
          for(int i=index;i<s.length();i++){
              if(wordDict.contains(s.substring(index,i+1))&&!list.contains(i)){
                  if(i==s.length()-1) return true;
                  list.add(i);
                  if(dfs(s,wordDict,list,i+1)) return true;
              }
          }
          return false;  
    }
}

2.动态规划+背包问题

上一种做法List列表就可以看作是一个动态规划数组。dp[i]表示以i结尾的子串是否能够匹配。遍历时采用两层嵌套循环，其中外层循环i控制子串的右边界，内层循环遍历子串的每一个位置j。也就是说要判断【0，i】能够匹配，需要枚举j判断【0，j】与【j，i】能否同时匹配。

状态转移公式为：dp[i]=dp[j]&&wordDict.contains(s.substring(j,i+1))

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