题目

给定一个字符串和一个字符串数组, 使用数组中的字符拼接给定的字符串, 数组的字符可以重复使用.

Input:  "leetcode",  ["leet", "code"]
Output: true
Input:  "applepenapple",  ["apple", "pen"]
Output: true
Input:  "catsandog",  ["cats", "dog", "sand", "and", "cat"]
Output: false
Input:  "cars",  ["car","ca", "rs"]
Output: true

思路1

DP, dp[i]表示字符串的前i个字符是否可以达成目标.

bool wordBreak5(string s, vector<string>& wordDict) {
    vector<bool> dp(s.size() + 1, false);
    dp[0] = true;

    for (int i = 0;i < s.size();i++) {
        for (int j = 0; j < wordDict.size(); j++) {
            string word = wordDict[j];
            string ss = s.substr(i, word.size());
            if (ss == word) {
                if (!dp[i + word.size()]) {
                     // 避免被覆盖
                    dp[i + word.size()] = dp[i];
                }
            }
        }
    }
    return dp[s.size()];
}

思路2

递归, 增加标记位. 类似DP, 当之前已经判断符合条件, 后面就不再重复判断.

bool wordBreakRecrution(string &s, int index, vector<string>& words, vector<int> &flags) {
    if (index == s.size()) {
        return true;
    }

    for (int i = 0; i < words.size();i++) {
        string word = words[i];
        int len = (int)word.size();
        if (s.substr(index, len) == word) {
            if (flags[index] != -1) {
                return flags[index];
            } else if (wordBreakRecrution(s, index + len, words, flags)) {
                flags[index] = true;
                return true;
            }
        }
    }
    flags[index] = false;
    return false;
}

bool wordBreak8(string s, vector<string>& wordDict)
{
    vector<int> flags(s.size() + 1, -1);
    return wordBreakRecrution(s, 0 , wordDict, flags);
}