139单词拆分

题目描述

给定一个非空字符串 s 和一个包含非空单词列表的字典 wordDict，判定 s 是否可以被空格拆分为一个或多个在字典中出现的单词。

说明：

• 拆分时可以重复使用字典中的单词。
• 你可以假设字典中没有重复的单词。

问题分析

//动态规划的基本操作：

• 定义dp数组
• 初始化

• 转化公式

  
  22.png

转移方程.png

解题思路1

class Solution {
public:
    bool wordBreak(string s, vector<string>& wordDict) {
        
        //基于hash表实现，无序且无重复
        auto wordDictSet = unordered_set <string>();
        for (auto word : wordDict)
        {
            wordDictSet.insert(word);
        }

        auto dp = vector<bool>(s.size() + 1);
        dp[0] = true;
        for (int i = 1; i <= s.size(); ++i)
        {
            for (int j = 0; j < i; ++j)
            {
                if (dp[j] && wordDictSet.find(s.substr(j, i - j)) != wordDictSet.end())
                {
                    dp[i] = true;
                    break;
                }
            }
        }
        return dp[s.size()];

    }
};