LeetCode 139 单词拆分：字符串s能否分割为字符串数组words（wordDict）中字符串的组合？（某未来公司面试题目）

水深无声 2022-05-09 01:50 142阅读 0赞

本文持续更新地址：[https://haoqchen.site/2018/11/08/LeetCode139/][https_haoqchen.site_2018_11_08_LeetCode139]

做了公司的面试题目后，上网一找。。发现竟然是Leetcode的题换了个外衣。。。~~~~~

顺便把变态的II也做了，[Leetcode 140 单词拆分II： 字符串s在字典wordDict中有多少种拆分方法。][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()];
        }
    };

但是大佬的代码在字典非常多的情况下的时间复杂度会偏高。

[https_haoqchen.site_2018_11_08_LeetCode139]: https://haoqchen.site/2018/11/08/LeetCode139/
[Leetcode 140 _II_ _s_wordDict]: https://haoqchen.site/2018/11/08/LeetCode140/