LeetCode139. 单词拆分（2024冬季每日一题 29）

给你一个字符串 s 和一个字符串列表 wordDict 作为字典。如果可以利用字典中出现的一个或多个单词拼接出 s 则返回 true。

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

示例 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

提示：

• $1<=s.length<=300$
• $1<=wordDict.length<=1000$
• $1<=wordDict[i].length<=20$
• s 和 wordDict[i] 仅由小写英文字母组成
• wordDict 中的所有字符串 互不相同

思路：动态规划

• 为了方便计算状态转移方程，我们在字符串的最前面，下标为 0 的位置添加任意字符（非小写字符）
• 我们定义 f[i] 表示字符串 s 前 i 个字符组成的字符串 s[1…i] 是否能被空格拆分成若干个字典中出现的单词
• 从前往后计算考虑转移方程，每次转移的时候我们需要枚举包含位置 i 的最后一个单词，看它是否出现在字典中以及除去这部分的字符串是否合法即可
• 所以可以枚举最后一个单词，判断去除最后一个合法单词后，前面的部分是否合法
• 可推断出状态转移方程：f[i] = max(f[i], f[i-t.size()])
  • 其中 t 是枚举的最后一个合法单词，max 求的是的最大值，可能取值为 0/1 代表 true/false，也就是只要有一个合法单词存在，说明当前 i 是可以拼接成的

class Solution {
public:
    int f[310];
    bool wordBreak(string s, vector<string>& wordDict) {
        int n = s.size(), m = wordDict.size();
        memset(f, 0, sizeof f);
        f[0] = 1;
        s = "." + s;
        for(int i = 1; i <= n; i++){
            string str = s.substr(1, i);
            for(int j = 0; j < m; j++){
                string t = wordDict[j];
                if(endWith(str, t)){
                    f[i] = max(f[i], f[i-t.size()]);
                }
            }
        }
        return f[n];
    }
    bool endWith(string & s, string & t){
        if(s.size() >= t.size()){
            return s.rfind(t) == (s.size() - t.size());
        }else{
            return 0;
        }
        
    }
};