题目

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

提示：

• 1 <= s.length <= 300
• 1 <= wordDict.length <= 1000
• 1 <= wordDict[i].length <= 20
• s 和 wordDict[i] 仅有小写英文字母组成

• wordDict中的所有字符串 互不相同

  解题方法

  动态规划

  由于字典中的词可以无限次使用，所求解得是字典中的词能否按某种顺序排列形成字符串s。将该题转换为 完全背包 问题，设定动态数组dp[j]表示字符串s下标0~j-1的子串可以通过字典中某些词按一定顺序组成，则有如下递推关系：
  
  其中issame用于判断字典元素插入到结尾为j位置时是否与字符串s中各位置相等。
  C++代码：

  class Solution {
  public:
    bool issame(string s, string w, int j) {
        for(int i=w.size()-1; i>=0; i--, j--) {
            if(w[i]!=s[j])  return false;
        }
        return true;
    }
  
    bool wordBreak(string s, vector<string>& wordDict) {
        int n = s.size();
        vector<bool> dp(n+1, false);
        dp[0] = true;
        for(int i=0; i<=n; i++) {
            for(int j=0; j<wordDict.size(); j++) {
                int m = wordDict[j].size();
                if(i>=m)    dp[i] = dp[i] || (dp[i-m] && issame(s, wordDict[j], i-1));
            }
            cout<<dp[i]<<" ";
        }
        return dp[n];
    }
  };