139. 单词拆分

给你一个字符串 s 和一个字符串列表 wordDict 作为字典。请你判断是否可以利用字典中出现的单词拼接出 s 。

注意：不要求字典中出现的单词全部都使用，并且字典中的单词可以重复使用。

 1 class Solution {
 2     public boolean wordBreak(String s, List<String> wordDict) {
 3         Set<String> set=new HashSet<>();
 4         for (int i=0;i<wordDict.size();i++){
 5             set.add(wordDict.get(i));
 6         }
 7         boolean[] dp=new boolean[s.length()+1];
 8         dp[0]=true;
 9         for (int i=1;i<=s.length();i++) {
10             for (int j=0;j<i;j++){
11                 boolean f=dp[j]&&set.contains(s.substring(j,i));
12                 dp[i]=dp[i]||f;
13                 if (dp[i]) break;
14             }
15         }
16         return dp[s.length()];
17     }
18 }

思路：动态规划，dp[i]表示0~i长度的字符串是否能匹配。0~i穷举分割点 就是dp[j]或j+1~i在字典中是否能找到。