LeetCode 139. 单词拆分

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

说明：

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

示例 1：

输入: s = "leetcode", wordDict = ["leet", "code"]
输出: true
解释: 返回 true 因为 "leetcode" 可以被拆分成 "leet code"。

示例 2：

输入: s = "applepenapple", wordDict = ["apple", "pen"]
输出: true
解释: 返回 true 因为 "applepenapple" 可以被拆分成 "apple pen apple"。
     注意你可以重复使用字典中的单词。

示例 3：

输入: s = "catsandog", wordDict = ["cats", "dog", "sand", "and", "cat"]
输出: false

 1 class Solution {
 2 public:
 3     bool wordBreak(string s, vector<string>& wordDict) {
 4         vector<bool> dp(s.size()+1,false);
 5         unordered_set<string> m(wordDict.begin(),wordDict.end());//无序set，查找更快，但占用空间大（hash表）
 6         dp[0] = true;
 7         int maxlength = 0;
 8         for(int i = 0; i < wordDict.size();i++)
 9         {
10             maxlength = max(int(wordDict[i].size()),maxlength);//这个地方为啥要加int，哪位哥哥能告诉我
11         }
12         for(int i = 1;i <= s.size();++i)
13             for(int j = max(i - maxlength,0);j < i;++j)
14             {
15                 if(dp[j]&&m.find(s.substr(j,i-j)) != m.end())
16                 {
17                     dp[i] = true;
18                     break;
19                 }
20             }
21         return dp[s.size()];
22     }
23 };

附上LeetCode调试：

 1 #include<set>
 2 #include<cstdio>
 3 #include<iostream>
 4 #include<unordered_set>
 5 #include<vector>
 6 using namespace std;
 7 
 8 class Solution {
 9 public:
10     bool wordBreak(string s, vector<string>& wordDict) {
11         vector<bool> dp(s.size()+1,false);
12         unordered_set<string> m(wordDict.begin(),wordDict.end());
13         dp[0] = true;
14         int maxlength = 0;
15         for(int i = 0; i < wordDict.size();i++)
16         {
17             maxlength = max(int(wordDict[i].size()),maxlength);
18         }
19         for(int i = 1;i <= s.size();++i)
20             for(int j = max(i - maxlength,0);j < i;++j)
21             {
22                 if(dp[j]&&m.find(s.substr(j,i-j)) != m.end())
23                 {
24                     dp[i] = true;
25                     break;
26                 }
27             }
28         return dp[s.size()];
29     }
30 };
31 int main()
32 {
33     Solution st;
34     string s = "leetcode";
35     vector<string> v;
36     v.push_back("leet");
37     v.push_back("code");
38     bool k = st.wordBreak(s,v);
39     cout << k << endl;
40 }