139 單詞拆分I

題目

給定一個非空字元串 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

方法：記憶化回溯（DFS）

如下圖所示

1、先選擇l，查找l是不是字典中詞，如果不是則回溯，查找le…

2、直到查找到leet發現是字典中的詞，那麼就将s重新指派為code繼續查找

代碼1

bool wordBreak(string s, vector<string>& wordDict)
    {
        return isContain(s,  wordDict);
    }

    bool isContain(string s, vector<string>& wordDict)
    {
        bool res = false;

        if(s.empty()) {
            return true;
        }
       
        for(int i = 0;i<s.size();i++)
        {
            const auto &iter = find(wordDict.begin(), wordDict.end(), 
            s.substr(0, i+1));
           
            if (iter != wordDict.end()) {
              res = isContain(s.substr(i+1), wordDict);
              if (res == true) {
                  break;
              }
            }
        }
        return res;
    }
           

其中for循環裡面的這段代碼

意思是從上圖中的頂層到底層全部情況中， 隻要找到符合題意的，立馬退出

也可以用這句代替

意思是從上圖中的頂層到底層全部情況中， 找到符合題意的将值儲存在res中，繼續周遊其他，保證後面周遊的結果不會影響之前符合題意的結果

但是送出了這段代碼之後，會顯示逾時

對，就是下面這一類的用例導緻逾時了

s = “aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaab”

wordDict =

[“a”,“aa”,“aaa”,“aaaa”,“aaaaa”,“aaaaaa”,“aaaaaaa”,“aaaaaaaa”,“aaaaaaaaa”,“aaaaaaaaaa”]

當i=0時，a在字典裡，

當i=1時，aa在字典裡

當i=2時，aaa在字典裡

…

但最後這個s (其長度為151）是無法達到拆分後全都在字典裡找到的。

是以，當i=0時，會進行一遍遞歸，直到s=b發現不符合題意，也就是s=150 、149、148…1都是不符合題意

當i=1時，s=149、148、147…1不符合題意

直到i=150,

是以這樣會導緻很多重複計算，是以我們需要在i=0的這一遍遞歸過程中就将所有不符合題意的字串标記

代碼2

class Solution {
public:
    bool wordBreak(string s, vector<string>& wordDict)
    {
        return isContain(s,  wordDict);
    }

    bool isContain(string s, vector<string>& wordDict)
    {
        bool res = false;

        if(s.empty()) {
            return true;
        }
        
        if(eraseRepated[s] == -1) {
            return false;
        }
        
        for(int i = 0;i<s.size();i++)
        {
            const auto &iter = find(wordDict.begin(), wordDict.end(), 
            s.substr(0, i+1));
           
            if (iter != wordDict.end()) {
              res = res || isContain(s.substr(i+1), wordDict);
              if (res == false) {
                  eraseRepated[s] = -1;
              }
            }
        }
        return res;
    }

private:
    map<string, int> eraseRepated; //初始值全為0
};