139、单词拆分
老样子，还是先尝试找出状态转移方程
状态转移方程
对问题进行分解，尝试从子问题入手解决。这也是前文提到过的 “分解问题” 的思想
对于输入的字符串 s，如果我能够从单词列表 wordDict 中找到一个单词匹配 s 的前缀 s[0..k]，那么只要我能拼出 s[k+1..]，就一定能拼出整个 s。换句话说，我把规模较大的原问题 wordBreak(s[0..]) 分解成了规模较小的子问题 wordBreak(s[k+1..])，然后通过子问题的解反推出原问题的解。
先找到字符串的一个前缀，如果我能拼出它剩下的部分，那么我就能拼出整个字符串。相当于将“拼出字符串”这个问题分解为“前缀” + “剩下部分”
base case
想要从wordDict中拼出字符串s，将其分为“前缀” 和 “剩下部分” 两部分。先判断 “前缀” 在 wordDict中是否存在，如果存在再判断 “剩下部分” 是否能拼出
考虑边界，当前缀的长度和字符串s的长度相等时，说明该字符串可以被拼出
if( 前缀 == s.length()){
return true;
}明确状态
前文已经讲过多次，“状态”就是原问题或者子问题中会变化的变量。
在此题中，状态就是 “当前字符串是否能被拼出”
确定选择
选择就是导致状态变化的行为，在此题中对应的是字符串s的 “前缀”。
定义dp函数
定义dp(string s,int i) 表示：字符串s从i下标开始是否能够拼出
联系框架
遍历所有可能的前缀，从而得出所有状态的结果
使用了备忘录的自上而下的递归解法
class Solution {
HashSet<String> wordDict;
int[] memo;
public boolean wordBreak(String s, List<String> wordDict) {
//将wordDict转为hashset，以便于后面使用contains方法
this.wordDict = new HashSet<>(wordDict);
//设置备忘录并初始化
this.memo = new int[s.length()];
//-1表示尚未判断，0表示无结果，1表示有结果
Arrays.fill(memo,-1);
return dp(s,0);
}
boolean dp(String s,int i){
//base case : 当前缀长度和字符串s长度相等时说明s可以被拼出
if(i == s.length()){
return true;
}
//如果备忘录中存在该数据，直接取用
if(memo[i] != -1){
return memo[i] == 0 ? false : true;
}
//遍历选择列表：所有可能的前缀
for(int len = 1;len + i <= s.length();len++){
//获得前缀字符串并判断是否存在于wordDict中
String prefix = s.substring(i,i + len);
//如果存在，那么问题转变为判断从(i+len)下标开始是否能拼出
if(wordDict.contains(prefix)){
boolean subPreblem = dp(s,i + len);
if(subPreblem ){
memo[i] = 1;
return true;
}
}
}
memo[i] = 0;
return false;
}
}- wordBreak 函数接受一个字符串 s 和一个单词字典 wordDict 的列表作为输入。它将单词字典转换成 HashSet，以便进行快速查找。同时，它初始化了一个长度为字符串 s 长度的备忘录数组 memo，并将其中所有元素都设为 -1。然后，它调用 dp 函数，并传入字符串 s 和起始索引 0。
- memo数组元素的含义是 memo[i] ：从索引i开始的子串能否被拼出来的结果
- dp 函数用于判断从索引 i 开始的子串是否可以被拼出来。它首先检查是否达到了字符串末尾，如果是的话，直接返回 true，表示该子串可以被拼出。然后，它检查备忘录数组 memo 中是否已经计算过该索引位置的结果，如果是的话，就直接返回相应的值。如果 memo[i] 的值为 0，表示子串无法被拼出，返回 false；如果 memo[i] 的值为 1，表示子串可以被拼出，返回 true。
如果备忘录数组中没有存储对应索引位置的结果，那么函数进入循环，遍历从索引 i 开始的所有前缀。对于每个前缀，它检查该前缀是否存在于单词字典中。如果存在，就递归调用自身，并更新索引为 i+len，判断剩余部分是否可以被拼出来。如果递归调用的结果为 true，表示剩余部分可以被拼出，那么将 memo[i] 的值设为 1，并返回 true。文章来源：https://www.toymoban.com/news/detail-813786.html
如果没有找到匹配的前缀，那么将 memo[i] 的值设为 0，表示子串无法被拼出，返回 false。文章来源地址https://www.toymoban.com/news/detail-813786.html
到了这里，关于动态规划篇-06：单词拆分的文章就介绍完了。如果您还想了解更多内容，请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章，希望大家以后多多支持TOY模板网！
