LeetCode 139 单词拆分:字符串s能否分割为字符串数组words(wordDict)中字符串的组合?(某未来公司面试题目)

编程之美

Posted by 白夜行的狼 on November 8, 2018

0. 写在最前面

本文持续更新地址:https://haoqchen.site/2018/11/08/LeetCode139/

你的Star是作者坚持下去的最大动力哦~~~

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

顺便把变态的II也做了,Leetcode 140 单词拆分II: 字符串s在字典wordDict中有多少种拆分方法。

1. 题目描述

设计一个函数 WordBreak:

  • 传入参数 s:待分隔的字符串。
  • 传入参数 words:可以使用的字符串数组。
  • 返回值:一个 bool 值,表示是否存在这样的分割。是的话返回 true,否则返回 false。

提示: 字母区分大小写。 所有字符串只会包含字母 A - Z 和 a - z。 words 中的字符串都可以在拆分时使用多次。

2. 示例

(1)
s = “TuSimpleCoLtd” words = [“Co”, “Ltd”, “Ha”, “TuSimple”] 返回值为 true。(可以分割为”TuSimple” + “Co” + “Ltd”)

(2)
s = “TusenCoLtd” words = [“Co”, “Ltd”, “Ha”, “TuSimple”] 返回值为 false。

3. 代码

千辛万苦AC了

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
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;
}

4. 思路

由于只有可能是字母,字母数量只有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”]

然后发现大佬十来句就解决了。。。。感受到了恐惧

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
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()];
    }
};

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


喜欢我的文章的话Star一下呗Star

版权声明:本文为白夜行的狼原创文章,未经允许不得以任何形式转载