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.
For example, given:
s: "barfoothefoobarman"
words: ["foo", "bar"]
You should return the indices: [0,9].
(order does not matter).
题意：找出所给列表words中的单词相接的子句在s中出现的索引。
注意：words中的单词可能重复出现
思路：1.建立一个字典wdict，统计words中所有单词的个数
2.判断s中所有可能的子句是否符合要求
1）判断字据中每个单词是否出现在wdict中，没有的话，此子句不符合要求
2）子句符合要求的话，加入新的属于子句的字典，如果子句中某个单词出现的次数超过wdict中这个单词出现的个数，此子句不符合要求
1 class Solution(object): 2 def findSubstring(self, s, words): 3 """ 4 :type s: str 5 :type words: List[str] 6 :rtype: List[int] 7 """ 8 res = [] 9 length = len(words[0]) 10 num = len(words) 11 l = length*num 12 lens = len(s) 13 wdict = {} 14 sset = set()#建立集合，收集所有已经符合条件的字句，减少判断次数 15 for word in words: 16 wdict[word] = 1+(wdict[word] if word in wdict else 0) 17 first_char = set(w[0] for w in words)#建立集合收集所有单词中的第一个字母，减少isRequired的次数 18 for i in range(lens-l+1): 19 if s[i] in first_char: 20 tmp = s[i:i+l] 21 if tmp in sset or self.isRequired(tmp,wdict,length): 22 sset.add(tmp) 23 res.append(i) 24 return res 25 def isRequired(self,s,wdict,length): 26 comp = {} 27 i = 0 28 while(i<len(s)-length+1): 29 tmp = s[i:i+length] 30 if tmp not in wdict: 31 return False 32 else: 33 comp[tmp] = 1+(comp[tmp] if tmp in comp else 0) 34 if comp[tmp]>wdict[tmp]: 35 return False 36 i += length 37 return True 38 39