分类：HashTable
考察知识点：HashTable 数组遍历
最优解时间复杂度：O(nm+n)*
30. Substring with Concatenation of All Words
You are given a string, s, and a list of words, words, that are all of the same length. Find all starting indices of substring(s) in s that is a concatenation of each word in words exactly once and without any intervening characters.
Example 1:
Input:
s = "barfoothefoobarman",
words = ["foo","bar"]
Output: [0,9]
Explanation: Substrings starting at index 0 and 9 are "barfoor" and "foobar" respectively.
The output order does not matter, returning [9,0] is fine too.
Example 2:
Input:
s = "wordgoodstudentgoodword",
words = ["word","student"]
Output: []
代码：
解法:
class Solution:
def findSubstring(self, s, words):
"""
:type s: str
:type words: List[str]
:rtype: List[int]
"""
#先判定边界条件
if len(s)==0 or len(words)==0:
return []
#先把这个words存到
words_length=len(words)
word_length=len(words[0])
if len(s)<word_length*words_length:
return []
words_dict={}
for word in words:
if word not in words_dict:
words_dict[word]=1
else:
words_dict[word]+=1
res=[]
for i in range(len(s)-words_length*word_length+1):
words_dict_copy=words_dict.copy()
start=i
count=words_length
while(count>0):
if s[start:start+word_length] not in words_dict_copy:
i
break
if words_dict_copy[s[start:start+word_length]]==0:
break
words_dict_copy[s[start:start+word_length]]-=1
start+=word_length
count-=1
if count==0:
res.append(i)
return res
讨论：
1.这道题目是道Hard题，我就不深究它了，Beats的人少就少吧
2.这道题的思路是首先判断是否可以返回空的几个条件，然后再是把words全部放到dict中去，然后在每次循环的时候弄一个dict_copy,再循环判断dict_copy中的数据
貌似是我有史以来速度最慢的一次
