AlgoPressAppearance
0139-单词拆分
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 中的所有字符串 互不相同
思路分析
动态规划 : 最主要是找出 dp 表示什么意思
定义 dp[i] 表示字符串 s 的前 i 个字符能否拆分成 wordDict 中包含的单词
dp[0] = true,表示空串也算一个合法的单词
从 i=1 开始计算，如 "leetcode" 那么 dp[1],dp[2],dp[3]都是 False 因为 l,le,lee都不在 wordDict中 直到 leet，这是个合法的单词。 dp[4] = True 那么继续往后循环的时候，就是 dp[4]开始的坐标，在往后阶段单词 c,co,cod 这样去判断并且 && dp[4] 为 True 就是合法的单词，不需要计算前面的数据 所以有 dp[j] && wordDict.Contains(s.Substring(j,length)) 就是 dp的值
用两层循环，第一层就是计算每个 dp[i] 的值 第二层循环计算开始的值，到当前的 i 为止，遍历 dp[j] && wordDict.Contains(s.Substring(j,length)) 即两部分都满足， dp[i] = true
参考代码
csharp
public class Solution {
public bool WordBreak(string s, IList<string> wordDict) {
int n = s.Length;
bool[] dp = new bool[n+1];
dp[0] = true;
for(int i=1; i<=n; i++){
for(int j = 0; j<i; j++){
if(dp[j] && wordDict.Contains(s.Substring(j,i-j))){
dp[i] = true;
break;
}
}
}
return dp[n];
}
}
参考代码2：复习 2022-04-02
csharp
public class Solution {
public bool WordBreak(string s, IList<string> wordDict) {
//动态规划
// dp[i] 表示前i个字符是否可以拆分为 wordDict 中的单词，所以初始化数组要+1
int n = s.Length;
bool[] dp = new bool[n+1];
// 初始化 0 个字符表示选用 wordDict 中的空字符，是可以的
dp[0] = true;
// 状态转移 dp[i] 表示前面去除 dp[j] 已经匹配的字符，然后剩余的字符还在 wordDict 里面
for(int i=1; i<=n; i++){
for(int j=0; j<i; j++){
//这里也可以判断，只要满足条件就 break，不用一直计算下去
dp[i] = dp[i] ||( dp[j] && wordDict.Contains(s.Substring(j,i-j)));
}
Console.WriteLine("dp[{0}]={1}",i,dp[i]);
}
return dp[n];
}
}
复习：20220515
csharp
public class Solution {
public bool WordBreak(string s, IList<string> wordDict) {
//完全背包
bool[] dp = new bool[s.Length+1]; //表示dp[j]表示前j个字符是否可以拆成字典里面的值
dp[0] = true;
for(int j=1;j<=s.Length;j++){
for(int i=0; i<wordDict.Count; i++){
int len = wordDict[i].Length;
if(j>=len && wordDict[i] == s.Substring(j-len,len) ){ //如果最后的能匹配
dp[j] = dp[j] || dp[j-len];
}
}
}
return dp[s.Length];
}
}
复习：20220630
csharp
public class Solution {
public bool WordBreak(string s, IList<string> wordDict) {
//动态规划，完全背包问题
int n = s.Length;
bool[] dp = new bool[n+1]; //dp[i]表示前i个字符是否能拆分
dp[0] = true; // 默认0个字符是可以拆分的
for(int j=1; j<=n; j++){
for(int i=0; i < wordDict.Count; i++){
if(j >= wordDict[i].Length){
int len = wordDict[i].Length;
string str = s.Substring(j-len, len);
if(wordDict[i] == str){
dp[j] = dp[j] || dp[j-len];
}
}
}
}
return dp[n];
}
}