Leetcode练习(Python):哈希表类:第30题:串联所有单词的子串:给定一个字符串 s 和一些长度相同的单词 words。找出 s 中恰好可以由 words 中所有单词串联形成的子串的起始位置。 注意子串要与 words 中的单词完全匹配,中间不能有其他字符,但不需要考虑 words 中单词串联的顺序。
题目:
串联所有单词的子串:给定一个字符串 s 和一些长度相同的单词 words。找出 s 中恰好可以由 words 中所有单词串联形成的子串的起始位置。 注意子串要与 words 中的单词完全匹配,中间不能有其他字符,但不需要考虑 words 中单词串联的顺序。
思路:
暴力解法,使用了滑动窗口的思想,使用两个哈希表的比较来看使用存在问题的描述。
程序:
class Solution:
def findSubstring(self, s: str, words: List[str]) -> List[int]:
if not s or not words:
return []
result = []
length = len(s)
word_num = len(words)
word_length = len(words[0])
windowLength = word_num * word_length
if windowLength > len(s):
return []
myHashMap1 = {}
for word in words:
if word in myHashMap1:
myHashMap1[word] += 1
else:
myHashMap1[word] = 1
for index1 in range(length - windowLength + 1):
myHashMap2 = {}
for index2 in range(word_num):
auxiliary = s[index1 + index2 * word_length : index1 + (index2 + 1) * word_length]
if auxiliary in myHashMap2:
myHashMap2[auxiliary] += 1
else:
myHashMap2[auxiliary] = 1
if myHashMap1 == myHashMap2:
result.append(index1)
return result