題目：

給定一個非空字串 s 和一個字典 wordDict，判斷 s 是否可以由字典中的單詞串接而成。字典中的單詞可以重複使用，且字典中的單詞是無序的。

範例：

s = "leetcode"
wordDict = ["leet", "code"]
回傳：true
因為 "leetcode" 可以拆成 "leet" + "code"。

s = "applepenapple"
wordDict = ["apple", "pen"]
回傳：true
因為可以拆成 "apple" + "pen" + "apple"。

s = "catsandog"
wordDict = ["cats", "dog", "sand", "and", "cat"]
回傳：false

解題思路

dp[i] 為 s 字串前 i 個字母中是否能夠拆分成單詞，dp[0] 表示空字串。

將 vector wordDict 轉換成 unordered_set 以便加快搜尋。

實作：

class Solution {
public:
    bool wordBreak(string s, vector<string>& wordDict) {
        vector<int> dp(s.size()+1, false);
        dp[0] = true;
        unordered_set<string> dict(wordDict.begin(), wordDict.end());
        
        for (int i = 1; i <= s.size(); i++) {
            for (int j = 0; j < i; j++) {
                if (dp[j] && dict.find(s.substr(j,i-j)) != dict.end()) {
                    dp[i] = true;
                    break;
                }
            }
        }
        return dp[s.size()];
    }
};

參考：
#139. Word Break