Sui Xin's Blog

[LeetCode]30. 串联所有单词的子串（Substring with Concatenation of All Words）

Posted on In Disqus:

题目描述

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

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

示例 1：

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

示例 2：

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

解题思路

  1. 解法一：暴力。直接遍历字符串，从每个位置往后找。
  2. 解法二：滑动窗口。使用两个指针，通过判断窗口内的单词个数以及单词哈希表的匹配来决定指针的移动。

代码

Python 3.6

解法一：暴力法

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
class Solution:
    def findSubstring(self, s: str, words):
        if not words:
            return []
        word_len = len(words[0])
        all_words_len = len(words) * word_len
        s_len = len(s)
        if s_len < word_len:
            return []
        res = []
        for i in range(s_len - all_words_len + 1):
            if s[i:i + word_len] in words:
                if self.find(s[i:], words, word_len):
                    res.append(i)
        return res
    
    def find(self, s, word_list, word_len):
        word_hash = {}
        for word in word_list:
            word_hash[word] = word_hash.setdefault(word, 0) + 1
        i = 0
        while True:
            tmp = s[i:i + word_len]
            if sum(word_hash.values()) == 0:
                return True
            elif (i + word_len <= len(s)) and tmp in word_hash and word_hash[tmp] > 0:
                word_hash[tmp] -= 1
                i += word_len
            else:
                return False

执行用时 : 1028 ms
内存消耗 : 14 MB

解法二：滑动窗口

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
class Solution:
    def findSubstring(self, s: str, words: List[str]) -> List[int]:
        from collections import Counter
        if not s or not words:
            return []
        s_len = len(s)
        word_len = len(words[0])  # 单词长度
        words_num = len(words)  # 单词个数
        if s_len < words_num * word_len:
            return []
        words_hash = Counter(words)  # 单词-个数 hashmap
        res = []
        
        for i in range(word_len):
            left, right = i, i
            count_word = 0  # 用来统计当前窗口内的单词个数
            window_words = Counter()  # 用来统计当前窗口内的单词-个数 hashmap
            while right + word_len <= s_len:
                cur_word = s[right:right + word_len]  # 新进窗口的单词
                right += word_len
                if cur_word not in words_hash:
                    # 若新进窗口的单词不在单词列表中，则窗口归 0
                    left = right
                    count_word = 0
                    window_words.clear()
                else:
                    window_words[cur_word] += 1
                    count_word += 1
                    while window_words[cur_word] > words_hash[cur_word]:
                        # 若新进窗口的单词个数超了，说明该单词的前一个位置之前的子串都没用
                        left_word = s[left:left + word_len]
                        window_words[left_word] -= 1
                        left += word_len
                        count_word -= 1
                    if count_word == words_num:
                        # 若当前窗口内单词数量与需求相同，说明该窗口是一个结果
                        res.append(left)
        return res

执行用时 : 148 ms
内存消耗 : 13.9 MB

参考

https://leetcode-cn.com/problems/substring-with-concatenation-of-all-words/solution/chuan-lian-suo-you-dan-ci-de-zi-chuan-by-powcai/

Related Posts