139. 单词拆分

1. 背

开始想到了递归，但是超时了。
下标好坑，但是我实在时找不到规律，dp[i] = (dp[i-str.length()+1] && dp[i-str.length()]) | | dp[i]
总之就是必须以i结尾时是否能够完全由数组组成。不好说，还是看代码吧。
这道题思路完全正确，但是下标实在是太糟了。

2. 题目

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

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

示例 1：

输入: s = “leetcode”, wordDict = [“leet”, “code”]
输出: true
解释: 返回 true 因为 “leetcode” 可以由 “leet” 和 “code” 拼接成。
示例 2：

输入: s = “applepenapple”, wordDict = [“apple”, “pen”]
输出: true
解释: 返回 true 因为 “applepenapple” 可以由 “apple” “pen” “apple” 拼接成。
注意，你可以重复使用字典中的单词。
示例 3：

输入: s = “catsandog”, wordDict = [“cats”, “dog”, “sand”, “and”, “cat”]
输出: false

来源：力扣（LeetCode）
链接：https://leetcode.cn/problems/word-break
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

3. 答案

下面的ij表示，i是最右边界，j从左往右遍历。
for里面的break其实可以没有，但是为了剪枝，能提速。
还有就是对于j的for结束之后还有一个判断，司判断[0,i]的有效性，其实这个也可以放在上面的for里面，但是怕扣不明白边界，单拉出来也还好

class Solution {
public:
    bool wordBreak(string s, vector& wordDict) {
        int n =static_cast(s.length());
        unordered_setwordSet;
        vectordp(n, false);
        for(auto str : wordDict)
            wordSet.insert(str);
        string tmp = string(1,s[0]);
        if(wordSet.find(tmp)==wordSet.end())
            dp[0] = false;
        else
            dp[0] = true;
        for(int i=1;i=0;--j)
            {
                auto xxx = s.substr(j+1,i-j);
                dp[i]  = dp[i] || (dp[j] && (wordSet.find(xxx)!=wordSet.end()));
                if(dp[i])
                    break;
            }
            auto xxx = s.substr(0, i+1);
            dp[i] = dp[i] || wordSet.find(xxx)!=wordSet.end();
        }
        return dp.back();
    }
};
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