LeetCode 139. Word Break [Medium] [C++] 解題筆記

 這題給定一個非空的 string s 和一個字串陣列 wordDict，要你判斷 s 是否可由 wordDict 中的字串串接而成，wordDict 中的字串可重複使用。

Example 1:

Input: s = "leetcode", wordDict = ["leet", "code"]
Output: true
Explanation: Return true because "leetcode" can be segmented as "leet code".

Example 2:

Input: s = "applepenapple", wordDict = ["apple", "pen"]
Output: true
Explanation: Return true because "applepenapple" can be segmented as "apple pen apple".
             Note that you are allowed to reuse a dictionary word.

Example 3:

Input: s = "catsandog", wordDict = ["cats", "dog", "sand", "and", "cat"]
Output: false

想法:

    這題可以用 DP 的方式來解，假設 dp[i] 表示 s[0 : i - 1] 可不可以用 wordDict 中的字串組合而成，則我們可以

將 s[0 : i - 1] 分割成 s[0 : j - 1] 和 s[j,i - 1] 來求解，因此我們只要針對 s 每個長度的子字串遍歷即可求得 dp 陣列。

完整程式碼:

/* dp solution */
class Solution {
public:
    bool wordBreak(string s, vector<string>& wordDict) {
        vector<bool> dp(s.size()+1, false);
        dp[0] = true;
        for (int i = 0; i < dp.size(); i++) {
            // check whether substr of s from(0~i) can be separate or not
            for (int j = 0; j < i; j++) {
                if (dp[j] && find(wordDict.begin(), wordDict.end(), s.substr(j, i-j)) != wordDict.end()) {
                    dp[i] = true;
                    break;
                }
            }
        }
        
        return dp.back();
    }
};