LeetCode 刷题 -- 139. 单词拆分

给你一个字符串 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
 

思路：

       定义状态转移数组 dp ，dp[ i ] 表示 s[0, ..., i - 1] 是否可以由 字符串词典 wordDict 中的字符串拼接而成。

       那么状态转移方程为：

           dp[ i ]  = dp[ j ] && s[j, ..., i-1] 是否可以由  字符串词典 wordDict 中的字符串拼接而成

c++

class Solution {
public:
    bool wordBreak(string s, vector<string>& wordDict) {
         // 定义 dp ，dp[i] 代表s[0] ... s[i-1] 组成的字符串是否可以由 wordDict 中的字符串组合而成
         vector<bool>  dp(s.size()+1,false);
         
 
         // 空字符串时，默认是可以匹配的
         dp[0] = true;
         for (int i=0;i<s.size()+1;i++) {
             for(int j=0;j<i;j++) {
                 // dp[j] 可以由 wordDict 中的字符串拼接完成，那么若是 字符串 s[j,...,i] 也可以由 wordDict 中的字符串拼接完成的话，那么说明 dp[i] 为 true 
                 string sub_s = s.substr(j,i-j);
                cout<< j <<" " <<i<< " " <<sub_s << endl;
 
                 if(dp[j] && find(wordDict.begin(), wordDict.end(),sub_s) != wordDict.end()) {
                     dp[i] = true;
                 }
             }
         }
 
        return dp[s.size()];
    }
};