刷题日记-139. 单词拆分

发布时间:2024年01月21日

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

比如 变量的创建(注意类型),查找字符串,分割字符串等,注意区分。

文章来源:https://blog.csdn.net/m0_62742402/article/details/135726052
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。