139. 單詞拆分

給你一個字符串 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;
    }
}