单词拆分

发表于 分类于 ， 阅读次数： Waline： 本文字数： 2.3k 阅读时长 ≈ 2 分钟

139. 单词拆分

给你一个字符串 s和一个字符串列表 wordDict作为字典。请你判断是否可以利用字典中出现的单词拼接出 s 。

注意：不要求字典中出现的单词全部都使用，并且字典中的单词可以重复使用。

示例：

输入: s = "leetcode", wordDict = ["leet", "code"]

输出: true

解释: 返回 true 因为 "leetcode" 可以由 "leet" 和 "code" 拼接成。

输入: s = "applepenapple", wordDict = ["apple", "pen"]

输出: true

解释: 返回 true 因为 "applepenapple" 可以由 "apple" "pen" "apple" 拼接成。

 注意，你可以重复使用字典中的单词。

思路：

让你判断 s 是否能被分解成 wordDict 中的单词，反过来想就是判断 wordDict 中的单词是否能拼出 s

dp(s,0,wordDict)表示当前位置为0， wordDict 中的单词是否能拼出 s，我们每次取wordDict中的单词word，然后从s中分割出s[i,i + word.size()]然后和word比较是否相等，如果相等我们继续，不相等我们就换个word。最后加上备忘录优化子问题。

方法一：递归
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
32
33
34
35
class Solution {
public:
    vector<int> memo;
    bool wordBreak(string s, vector<string>& wordDict) {
        memo.resize(s.size(), -1);
        return dp(s, 0, wordDict);
    }
    bool dp(string s, int i, vector<string> wordDict){
        //base case
        if(i == s.size()) return true;

        if(memo[i] != -1) return memo[i] == 1 ? true : false;

        //遍历所有单词，尝试匹配 s[i...] 的前缀
        for(string word : wordDict){
            int len = word.size();
            if(i + len > s.size()){
                continue;
            }
            string subStr = s.substr(i, len);
            if(subStr != word){
                continue;
            }
            //s[i...] 的前缀已经匹配，去尝试匹配 s[i + len..]
            if(dp(s, i + len, wordDict)){
                //s[i...] 可以被拼出， 将结果计入备忘录
                memo[i] = 1;
                return true;
            }
        }
        //不能拼出 s[i...]
        memo[i] = 0;
        return false;
    }
};
方法二：迭代
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution {
public:
    bool wordBreak(string s, vector<string>& wordDict) {
        vector<bool> dp(s.size() + 1, false);
        dp[0] = true;
        for(int i = 0; i < s.size(); i++){
            if(!dp[i]){
                continue;
            }
            for(auto& word : wordDict){
                int len = word.size();
                if(i + len <= s.size() && s.substr(i, len) == word){
                    dp[i + len] = true;
                }
            }
        }
        return dp[s.size()];
    }
};