用两种方法来做(还有第三种方法,以后再看吧0.0):

  1. 动态规划(简单,适合本题)
  2. 递归(有人把这叫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;
    }
};