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

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

示例 1：

输入: s = “leetcode”, wordDict = [“leet”, “code”]
输出: true
解释: 返回 true 因为 “leetcode” 可以由 “leet” 和 “code” 拼接成。
示例 2：

输入: s = “applepenapple”, wordDict = [“apple”, “pen”]
输出: true
解释: 返回 true 因为 “applepenapple” 可以由 “apple” “pen” “apple” 拼接成。
注意，你可以重复使用字典中的单词。
示例 3：

输入: s = “catsandog”, wordDict = [“cats”, “dog”, “sand”, “and”, “cat”]
输出: false

思考

定义dp数组及其下标的含义

dp[i]:表示wordDict前1-i个字母能否由单词组成

• dp[i] =1 ，代表前1-i个字母可以由单词组成
• dp[i] = 0,反之

初始化dp数组

创建dp[ s.length + 1]数组

令dp[ 0 ] =1;

这里dp[0]是起辅助作用，主要目的为的是让 dp[i-word.lenth] ,其i =word.length时，dp = 1;

状态转移方程

这里如果dp[i-word.length] = 1,并且截下来的词和word相同dp[i]=1

class Solution {
    public boolean wordBreak(String s, List<String> wordDict) {
        // step 1 创建dp数组
        int[] dp=new int[s.length()+1];

        // step 2 初始化dp数组
        dp[0] =1;

        // step 3 完善dp数组
        for (int i=1;i<dp.length;i++){
            for (String word : wordDict) {
                if(i>=word.length()){
                    if (dp[i-word.length()]==0) continue;
                    String sub=s.substring(i-word.length(),i);
                    if(sub.equals(word)) {
                        dp[i]=1;
                        break;
                    }
                }
            }
        }

        // step 4 printDp
        for (int i = 0; i < dp.length; i++) {
            System.out.println("dp "+i+","+dp[i]);
        }
        if (dp[dp.length-1]==1) return true;
        else return false;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30