139. Word Break

1.問題

• 判斷用list的字串是否可以組成s

2.想法

• 提問

• function header, parameter

• test input

• 觀察

• 說明想法

  • 這個問題最直覺的做法是用DFS來列舉所有的可能性, 但會超出時間

  • 其實可以用DP的做法, 設定end, start兩指標, 等於是雙重迴圈, 搜尋start與end所截取的片段是否有在list中, 如果有且dp[start]為真, 則讓dp[end + 1] = true, 最後判斷dp[size]

• 測試計算複雜度

3.程式碼

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