题源：LeetCode

链接：https://leetcode-cn.com/problems/word-break/

 

 

 

这道题目也是用到动态规划，同时考虑使用哈希表的数据结构。

 

 其中check指的是dp[j]后的词是否在哈希表中出现，若出现则dp[i]为true

 1 class Solution {
 2 public:
 3     bool wordBreak(string s, vector<string>& wordDict) {
 4 
 5         auto wordDictSet = unordered_set <string> ();
 6         for (auto word: wordDict) {
 7             wordDictSet.insert(word);
 8         }
 9 
10         auto dp = vector<bool>(s.size()+1);
11         dp[0] = true;
12 
13         for(int i = 1;i<=s.size();i++){
14             for(int j = 0;j<i;j++){
15                 if(dp[j]&&wordDictSet.find(s.substr(j,i-j))!=wordDictSet.end()){
16                     dp[i] = true;
17                     break;
18                 }
19             }
20 
21         }
22         return dp[s.size()];
23 
24     }
25 };