139 单词拆分 dp - 青衣怒马 - D1h.Net第一号博客
 






lazy pig~

青灯古佛,不见笑傲江湖...
 
 

Powered by D1h.Net第一号博客
D1h.Net第一号博客 | 首页 | 新随笔 | 联系 | 订阅 订阅 | 管理

139 单词拆分 dp

 

 

dp[i]表示[0,...i-1]是否是合法字符串,因为dp[i]的状态不只是由dp[i-1]决定的,而是前边每个地方都有可能成为断点,只要有一个结果是true,则结果就是true,所以对于每个dp[i]遍历其之前的每个断点

class Solution { public: bool wordBreak(string s, vector<string>& wordDict) { unordered_set <string> wordDictSet ; 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()]; } };

 

 

每天进步一点点~
发表于 2021-09-17 00:33  青衣怒马  阅读(4)  评论(0编辑  收藏  举报
 

问答 28u iTmz.Net 3q科技 A8团队1 A8团队2 A8团队3 A8备