139. 單詞拆分

zzu菜 2022-06-23 15:47:14 阅读数:311

拆分

給你一個字符串 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;
}
}
版权声明:本文为[zzu菜]所创,转载请带上原文链接,感谢。 https://gsmany.com/2022/174/202206231505374165.html