LeetCode 139 單詞拆分：字元串s能否分割為字元串數組words（wordDict）中字元串的組合？（某未來公司面試題目）

本文持續更新位址：https://haoqchen.site/2018/11/08/LeetCode139/

做了公司的面試題目後，上網一找。。發現竟然是Leetcode的題換了個外衣。。。~~~~~

順便把變态的II也做了，Leetcode 140 單詞拆分II： 字元串s在字典wordDict中有多少種拆分方法。

題目描述

設計一個函數 WordBreak：

+ 傳入參數 s：待分隔的字元串。

+ 傳入參數 words：可以使用的字元串數組。

+ 傳回值：一個 bool 值，表示是否存在這樣的分割。是的話傳回 true，否則傳回 false。

提示：

字母區分大小寫。

所有字元串隻會包含字母 A - Z 和 a - z。

words 中的字元串都可以在拆分時使用多次。

示例

（1）

s = "TuSimpleCoLtd"

words = ["Co", "Ltd", "Ha", "TuSimple"]

傳回值為 true。（可以分割為"TuSimple" + "Co" + "Ltd"）

（2）

s = "TusenCoLtd"

words = ["Co", "Ltd", "Ha", "TuSimple"]

傳回值為 false。

代碼（千辛萬苦AC）

class Solution {
public:
    bool wordBreak(string s, vector<string>& wordDict) {
        vector<vector<int>> words_map;
        words_map.resize(52);
        bool* has_break = new bool[s.size()];//建立一個與s同長度的bool類型變量，用于存儲以前在某個位置上是否已經進行過分割，比如在[5]這裡進行過分割，然後[5]後面沒能成功分割，那麼以後遇到在[5]這裡的分割就可以直接跳過了，沒有這個會逾時。
        memset(has_break, false, sizeof(bool)*s.size());
        for (int i = 0; i < wordDict.size(); ++i){//以首字母為鍵值建構自己的map
            char word = wordDict[i][0];
            words_map[letter2int(word)].push_back(i);
        }
        for (int i = 0; i < 52; ++i){//對map按照字元串大小進行從大到小排序，目的是想先用長的字元串進行分割，可以一定程度上節省時間，後來加入了has_break其實這裡不用也行
            sort(words_map[i].begin(), words_map[i].end(), [&wordDict](int a, int b)->bool{ return (wordDict[a].size() > wordDict[b].size()); });
        }
        bool can_break = dfs(s, wordDict, words_map, has_break);
        delete[] has_break;
        return can_break;
    }
private:
    int letter2int(char _letter)//字母轉map鍵值，先'a-z'再'A-Z'
    {
        if (_letter >= 'a' && _letter <= 'z')
            return (_letter - 'a');
        return (_letter - 'A' + 26);
    }
    
    bool dfs(const string& _s, const vector<string>& _words, vector<vector<int>>& _words_map, bool* _has_break)
    {
        if (_s.size() == 0)
            return true;
        bool can_break = true;
        for (auto index : _words_map[letter2int(_s[0])]){
            int i = 0;
            if((_words[index].size() > _s.size()) || (_has_break[_words[index].size() - 1]) )//如果字典字元串比原字元串大，以及已經在該位置進行過分割，直接跳過
                continue;
            for (; i < _words[index].size(); ++i){//比較所有首字母相同的words
                if (_s[i] ^ _words[index][i]){//利用異或比較首字母相同的word與s是否相同
                    can_break = false;
                    break;
                }
            }
            if (can_break){
                _has_break[_words[index].size() - 1] = true;//在某個位置上可以切割，記錄下來
                string substr = _s.substr(_words[index].size());
                bool* sub_has_break = _has_break + _words[index].size();
                if (dfs(substr, _words, _words_map, sub_has_break))//如果可以切割則dfs疊代
                    return true;//成功則傳回，否則繼續下一個word的判斷
            }
            can_break = true;
        }
        return false;
    }
};

int main(int argc, char** argv)
{
    Solution obj;
    string s = "abcd";
    vector<string> words;
    words.push_back("a");
    words.push_back("abc");
    words.push_back("b");
    words.push_back("cd");
    if (obj.wordBreak(s, words))
        cout << "True" << endl;
    else
        cout << "False" << endl;
    return 0;
}
           

思路：

由于隻有可能是字母，字母數量隻有52個，是以建構map可以減小比較的時間。這是建立在words中沒有重複的word假設之上的，如果words中存在重複的word，則直接将整個word作為鍵值或者建構排序二叉樹會更好一點。然後就是基本的DFS問題了。簡單的DFS會遇到一個問題，比如"a" "aa" "aaa"，其實前兩個加起來是等于第三個的，如果前兩個合起來之後在[3]這裡進行了切割得到的後續子字元串是不能成功切割的，其實第三個也不用試了，浪費時間，比如下面這種情況。部落客就出現了逾時的情況。這裡引入一個bool型的數組，用于記錄我們之前已經在哪個位置進行過切割，而且後續不行的。

"aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaab" ["a","aa","aaa","aaaa","aaaaa","aaaaaa","aaaaaaa","aaaaaaaa","aaaaaaaaa","aaaaaaaaaa"]

然後發現大佬十來句就解決了。。。。感受到了恐懼

class Solution {
public:
    bool wordBreak(string s, vector<string>& wordDict) {
        vector<bool> dp(s.size()+1,false);
        dp[0]=true;
        for(int i=1; i<=s.size(); i++){
            for(auto& p : wordDict){
                 int len = p.size();
                if( i<len || !dp[i-len] || s[i-1] != p[len-1] )
                    continue;
                if( s.substr(i-len, len) == p ){
                    dp[i]=true;
                }
            }
        }
        return dp[s.size()];
    }
};
           

但是大佬的代碼在字典非常多的情況下的時間複雜度會偏高。