【算法】【动规】单词拆分

2023-12-14 17:42:56

跳转汇总链接

👉🔗算法题汇总链接


1.4 单词拆分

🔗题目链接

给你一个字符串 s 和一个字符串列表 wordDict 作为字典。请你判断是否可以利用字典中出现的单词拼接出 s 。
注意:不要求字典中出现的单词全部都使用,并且字典中的单词可以重复使用。

  1. 状态表示
    • 本题依旧以 s 字符串上 i 位置为结尾作为一个状态。这个状态还能分成两部分,将最后一部分的开头设做 j 位置:[0, j) 能被字典中的词拼出来 + [j, i] 是在字典中的词,以这样分析,如果有一种情况下这两部分都是满足的,这个 i 位置就可以设成 true 了。
    • dp[i] 表示以 i 位置为结尾的字符串能否被字典中的单词拼出来。
  2. 状态转移方程
    • 这里的位置划分明显有两个变量 i 和 j

      有 0 < j <= i
      
    • 分析 i 位置的状态转移方程

      dp[i] = 
      	if (dp[j] == true && 
      		s.substr(j, i-j) 在 wordDict 中), true
      	else, false
      
  3. 初始化
    • 表头添加一个元素,初始化为 true
    • 对 s 字符串也添加一个占位符在前面,便于访问原始数据
  4. 填表顺序
    • 从左往右依次填写
  5. 返回值
    • dp 表的末尾值

🐎 代码如下:
(下面还有优化版本)

class Solution {
public:
    bool IsInDict(const string& str, const vector<string>& wordDict)
    {
        for(auto e : wordDict)
        {
            if (str == e)
            {
                return true;
            }
        }
        return false;
    }
    bool wordBreak(string s, vector<string>& wordDict) {
        int n = s.size();
        vector<int> dp(n + 1);
        dp[0] = 1;
        s = 'x' + s;
        for(int i = 1; i < n + 1; i++)
        {
            for(int j = 1; j <= i; j++)
            {
                if(dp[j-1] == 1 && IsInDict(s.substr(j, i-j+1), wordDict))
                {
                    dp[i] = 1;
                    break;
                }
            }
        }
        return dp[n];
    }
};



这里 IsInDict 的实现是不是有点傻?字典查询,属于“在不在”问题,用 hash 怎么样~

class Solution {
public:
    bool wordBreak(string s, vector<string>& wordDict) {
        unordered_set<string> hash;
        for(auto e : wordDict) hash.insert(e);

        int n = s.size();
        vector<bool> dp(n + 1); // bool在vector中默认值是0,跟int一样啦
        dp[0] = true;           // 保证后续结果正确
        s = 'x' + s;            // 保持统一,方便读取原数据
        for(int i = 1; i < n + 1; i++)
        {
            for(int j = 1; j <= i; j++)
            {
                if(dp[j-1] == 1 && hash.count((s.substr(j, i-j+1))))
                {
                    dp[i] = true;
                    break;
                }
            }
        }
        return dp[n];
    }
};

🥰如果本文对你有些帮助,欢迎👉 点赞 收藏 关注,你的支持是对作者大大莫大的鼓励!!(????) 若有差错恳请留言指正~~


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