30. 串联所有单词的子串 [hard]

https://leetcode-cn.com/problems/substring-with-concatenation-of-all-words/

给定一个字符串 s 和一些长度相同的单词 words。找出 s 中恰好可以由 words 中所有单词串联形成的子串的起始位置。

注意子串要与 words 中的单词完全匹配，中间不能有其他字符，但不需要考虑 words 中单词串联的顺序。

示例 1：

输入：
  s = "barfoothefoobarman",
  words = ["foo","bar"]
输出：[0,9]
解释：
从索引 0 和 9 开始的子串分别是 "barfoo" 和 "foobar" 。
输出的顺序不重要, [9,0] 也是有效答案。

示例 2：

输入：
  s = "wordgoodgoodgoodbestword",
  words = ["word","good","best","word"]
输出：[]

通过次数38,855 | 提交次数124,411

Second Try

2020-07-24

参考题解，利用了单词长度相等的特性，直接上统计规避单词组合问题。但这种解法真的就是利用题解相同长度单词的场景出来的解法，没有first try里的trie树来得通用。

class Solution:
    def findSubstring(self, s: str, words: List[str]) -> List[int]:
        if len(s) == 0 or len(words) == 0:
            return []
        slen, wlen, wc = len(s), len(words[0]), len(words)
        counter = collections.Counter(words)
        start_set = set([w[0] for w in words]) # speed up 
        # print('counter', counter)
        rv = []
        for i in range(slen - wc * wlen + 1):
            if s[i] not in start_set:
                continue
            tmp_counter = collections.Counter()
            # 这个range的写法真是纠结，容易出bug...
            for j in range(i, i + (wc - 1) * wlen + 1, wlen):
                # print(i,j, s[j:j+wlen], i + (wc-1) * wlen)
                if s[j: j+wlen] not in counter:
                    break 
                tmp_counter[s[j: j + wlen]] += 1
            flag = True 
            for k, v in counter.items():
                if tmp_counter[k] != v:
                    flag = False
                    break 
            if flag:
                rv.append(i)
        return rv 

执行用时：1088 ms, 在所有 Python3 提交中击败了32.78%的用户
内存消耗：13.8 MB, 在所有 Python3 提交中击败了9.52%的用户

First Try

2020-07-24

用上了trie树，直接上暴力解法，复杂度是O(N * len(total words))，结果还是遇到两个问题：

单词列表里竟然允许有重复的单词，trie树一般就无视了。不得已修改为允许存储多个index的trie树。
在复杂测试安利下还是超时了，kmp算法又不会写。最后对起点i的范围进行限制，一开始是range(len(s)), 后来修改成range(len(s) - words * len(word) + 1),终于成功解决words超长的测试样例。

不会kmp算法，还是有点没底啊。不过看题解发现还有一个条件没用上，这些单词都是相同长度的，没用上一个条件也能暴力通过，还是trie树太优秀了。还没发现单词相等有什么作用。。。

贡献了题解： https://leetcode-cn.com/problems/substring-with-concatenation-of-all-words/solution/trieshu-tong-yong-jie-fa-by-geehan/

"""
"wordgoodgoodgoodbestword"
["word","good","best","good"]

"""

class Solution:
    def findSubstring(self, s: str, words: List[str]) -> List[int]:
        # hard题还要上暴力吗。。。
        """
        - 靠，单词列表竟然还能重复，这不就搞笑了么，trie树还能怎么玩。。。
        - 只能额外添加列表进行选择。 结果tmd竟然还是超时了。
        - 对遍历长度进行限制，终于通过了。。。
        """
        if len(s) == 0 or len(words) == 0:
            return []
        wlen, wc =  len(words[0]), len(words)
        trie = dict()
        mark = "#idx"
        for idx, word in enumerate(words):
            node = trie 
            for c in word:
                node = node.setdefault(c, dict())
            if mark not in node:
                node[mark] = set()
            node[mark].add(idx)

        # print("trie", trie)
        rv = []
        # 对长度进行限制，勉强通过了。。。
        for i in range(len(s) - wc * wlen + 1):
            if s[i] in trie:
                visited = set()
                node = trie
                j = i 
                while j < len(s) and s[j] in node:
                    node = node[s[j]]
                    if mark in node:
                        available_marks = node[mark] - visited
                        if not len(available_marks):
                            break 
                        visited.add(available_marks.pop())
                        node = trie
                    j += 1
                if len(visited) == len(words):
                    rv.append(i)
        return rv 

执行用时：2068 ms, 在所有 Python3 提交中击败了13.63%的用户
内存消耗：14.9 MB, 在所有 Python3 提交中击败了9.52%的用户

30. 串联所有单词的子串 [hard]​

Second Try​

First Try​

30. 串联所有单词的子串 [hard]

Second Try

First Try