一、題目大意
標簽: 動態規劃
https://leetcode.cn/problems/word-break
給你一個字符串 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
提示：
- 1 <= s.length <= 300
- 1 <= wordDict.length <= 1000
- 1 <= wordDict[i].length <= 20
- s 和 wordDict[i] 僅有小寫英文字母組成
- wordDict 中的所有字符串 互不相同
二、解題思路
這道題的分割條件由集合內的字符串决定，因此在考慮每個分割比特置時，需要遍曆字符串集合，以確定當前比特置是否可以成功分割，注意對於比特置0，需要初始化值為真。
三、解題方法
3.1 Java實現
public class Solution {
public boolean wordBreak(String s, List<String> wordDict) {
int n = s.length();
boolean[] dp = new boolean[n + 1];
dp[0] = true;
for (int i = 1; i <= n; i++) {
for (String tmp : wordDict) {
int len = tmp.length();
if (i>=len && tmp.equals(s.substring(i - len, i))) {
dp[i] = dp[i] || dp[i - len];
}
}
}
return dp[n];
}
}
四、總結小記
- 2022/6/24 又到周五了，雙休的日子時間飛快
