用两种方法来做(还有第三种方法,以后再看吧0.0):
- 动态规划(简单,适合本题)
- 递归(有人把这叫DFS,我还纳闷了老半天,严格来说本题还有第三种方法BFS)
动态规划的话,理解比较清晰,写起来也比较简单。
递归的话,如果没有优化,会完全通过不了;优化过后,可以和DP媲美。
下面放出DP、DFS(有优化),DFS(无优化)的代码,供大佬们参考。
动态规划
// // Created by jt on 2020/8/8. // #include using namespace std; class Solution { public: bool wordBreak(string s, unordered_set &dict) { // 动态规划:1\. 每一个状态和前一个状态有关;2\. 最小子状态是可以求得的 // 转移方程:f(i)表示s[0,i]可以分词,那么f(i) = f(j) && f(j+1, i); (0<=j<i) int len = s.length(); vector dp(len+1, false); dp[0] = true; for (int i = 1; i <= len; ++i) { // 注意终止条件,此处从1开始,终止条件应该为len for (int j = i-1; j >= 0; --j) { if (dp[j] && dict.find(s.substr(j, i-j)) != dict.end()) { dp[i] = true; break; } } } return dp[len]; } };
DFS(优化后)
// // Created by jt on 2020/8/8. // #include using namespace std; class Solution { public: bool wordBreak(string s, unordered_set &dict) { vector status(s.size(), -1); // 这里不用布尔类型,因为需要存储三个状态(未访问、true和false) return dfs(s, dict, status, 0); } bool dfs(string &s, unordered_set &dict, vector &status, int start) { if (start > s.size() - 1) return true; if (status[start] != -1) return status[start]; for (int end = start + 1; end <= s.size(); ++end) { if (dict.find(s.substr(start, end - start)) != dict.end() && dfs(s, dict, status, end)) { status[start] = 1; return true; } } status[start] = 0; return false; } };
DFS(无优化)
注释掉的部分好像能通过40%样例,但是是写错了的,哇哈哈。。。💩碰运气
// // Created by jt on 2020/8/8. // #include using namespace std; class Solution { public: bool wordBreak(string s, unordered_set &dict) { // 递归求解:(true)&&(true&&(true&&(true))) // 也可以理解为深度优先(DFS) int len = s.length(); if (len == 0) return true; for (int i = 1; i <= len; ++i) { // 下面方法只能通过40%样例,注意用例:"aaaaaaa",["aaaa","aaa"] // if (dict.find(s.substr(0, i)) != dict.end()) { // return wordBreak(s.substr(i), dict); // } // 这个递归是正确的,但是由于效率过低,一个样例都过不了,呜呜 if (dict.find(s.substr(0, i)) != dict.end() && wordBreak(s.substr(i), dict)){ return true; } } return false; } };