刷题日记-139. 单词拆分

这是一道动态规划题目，要求判断给出的字符串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库的使用上很多地方有所不同

比如 变量的创建（注意类型），查找字符串，分割字符串等，注意区分。