1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31

class Solution {
public:
    bool dfs(string s, vector<string>& wordDict, int u) {
        if (u == s.size()) {
            return true;
        }

        for (int i = 0; i < wordDict.size(); i ++) {
            // 判断是否满足条件
            bool flag = true;
            for (int j = 0; j < wordDict[i].size(); j ++) {
                if (u + j < s.size()) {
                    if (s[u + j] != wordDict[i][j]) {
                        cout << wordDict[i] << endl;;
                        flag = false;
                        break;
                    }
                }
            }
            if (flag) {
                if (dfs(s, wordDict, u + wordDict[i].size())) return true;;
            }
        }

        return false;
    }    

    bool wordBreak(string s, vector<string>& wordDict) {
        return dfs(s, wordDict, 0);
    }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21

class Solution {
public:
    bool wordBreak(string s, vector<string>& wordDict) {
        unordered_set<string> wordset;
        for (auto t : wordDict) {
            wordset.insert(t);
        }

        vector<bool> dp(s.size() + 1);
        dp[0] = true;
        for (int i = 1; i <= s.size(); i ++) {
            for (int j = 0; j < i; j ++) {
                if (dp[j] && wordset.find(s.substr(j, i - j)) != wordset.end()) {
                    dp[i] = true;
                    break;
                }
            }
        }
        return dp[s.size()];
    }
};