这是一道动态规划题目,要求判断给出的字符串s能否被wordDict字符串列表中的字符串组成。
这段代码是一个解决单词拆分问题的函数 `wordBreak`,其作用是判断字符串 `s` 是否可以被拆分为由字典 `wordDict` 中的单词组成。
我们要通过构建一个布尔值的向量 `dp`,来判断字符串 `s` 是否可以被拆分为字典中的单词。
class Solution {
public:
bool wordBreak(string s, vector<string>& wordDict) {
auto wordDictSet = unordered_set <string>();
for(auto word:wordDict){
wordDictSet.insert(word);
}
`wordBreak` 函数接受两个参数:一个字符串 `s` 和一个字符串向量 `wordDict`。
在函数内部,先创建一个空的 `unordered_set<string>` 类型的变量 `wordDictSet`。
使用范围循环遍历 `wordDict`,将其中的每个单词插入到 `wordDictSet` 中(把字典内容插入wordDictSet中是为了后面使用wordDictSet.find查找单词)
auto dp = vector<bool>(s.size()+1);
dp[0]=true;
for(int i=1;i<=s.size();i++){
创建一个存储布尔值的向量 `dp`,大小为 `s.size()+1`。
将 `dp[0]` 设置为 `true`,即空字符串可以被拆分为字典中的单词(即使用0个字典单词)。
for(int j=0;j<i;j++){
if(dp[j]&&wordDictSet.find(s.substr(j,i-j))!=wordDictSet.end()){
dp[i]=true;
break;
}
}
}
使用两个循环嵌套,外层循环遍历 `s` 的每个字符位置 `i`。
内层循环遍历从 0 到 `i` 的所有可能的拆分点 `j`。
在每个拆分点 `j` 处,检查子字符串 `s.substr(j, i-j)` 是否存在于 `wordDictSet` 中。
如果找到了一个拆分点 `j`,且 `dp[j]` 为 `true`,表示从起始位置到 `j` 的子字符串可以被拆分为字典中的单词,那么将 `dp[i]` 设置为 `true`。
最后,如果 `dp[s.size()]` 为 `true`,表示整个字符串 `s` 可以被拆分为字典中的单词,返回 `true`;否则返回 `false`。
注意:
在这段代码中,
wordDictSet.find(s.substr(j,i-j))
返回的是一个迭代器,而不是直接的结果值。如果找到了对应的子字符串,则返回指向该子字符串的迭代器;如果没有找到,则返回wordDictSet.end()
,表示迭代器指向字典集合的末尾。所以在这段代码中,应该使用
wordDictSet.find(s.substr(j,i-j)) != wordDictSet.end()
来判断是否找到了对应的子字符串,而不是与0或-1进行比较。
return dp[s.size()];
}
};
函数最后返回 `dp[s.size()]`,表示整个字符串 `s` 是否可以被拆分为字典中的单词。
上面是c++写法
接下来再用JavaScript实现:
/**
* @param {string} s
* @param {string[]} wordDict
* @return {boolean}
*/
var wordBreak = function(s, wordDict) {
const n=s.length;
const dp=new Array(n+1).fill(false);
dp[0]=true;
for(var i=1;i<=n;i++){
for(var j=0;j<i;j++){
if(dp[j]&&wordDict.indexOf(s.substring(j,i))!==-1){
dp[i]=true;
break;
}
}
}
return dp[n];
}
c++和JavaScript库的使用上很多地方有所不同
比如 变量的创建(注意类型),查找字符串,分割字符串等,注意区分。