题目描述
给定一个字符串 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”]
输出:[]
解题思路
- 解法一:暴力。直接遍历字符串,从每个位置往后找。
- 解法二:滑动窗口。使用两个指针,通过判断窗口内的单词个数以及单词哈希表的匹配来决定指针的移动。
代码
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) res = [] for i in range(word_len): left, right = i, i count_word = 0 window_words = Counter() while right + word_len <= s_len: cur_word = s[right:right + word_len] right += word_len if cur_word not in words_hash: 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/