【LeetCode每天一题】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:
SRE实战 互联网时代守护先锋，助力企业售后服务体系运筹帷幄！一键直达领取阿里云限量特价优惠。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 = "wordgoodgoodgoodbestword", words = ["word","good","best","word"] Output: []
思路
在一开始做这道题时，想着从头到尾一直遍历使用暴力破解法来解决，但是在编码完成之后，一直不通过。最终看了以下答案。发现整体思路都是一样的只不过在细节上处理上更加厉害。
这道题的整体思路是先将words列表中的单词转化为字典，然后进行遍历来判断是否存在字符串中。详细见代码。
解决代码
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 from collections import Counter 9 if not s or not words: 10 return [] 11 word_size = len(words[0]) # 因为每一个单词长度一样，求出其中一个单词的长度
12 word_map = Counter(words) # 将words列表中的单词进行计数统计 13 results = [] # 存储结果
15 num_word = len(words) # 单词的总数 16 list_size = word_size*num_word # 所有单词的总长度 17 for i in range(len(s)-list_size+1): # 只需要遍历到 s的长度减去单词的总长度的位置就行了，因为后面的不会满足条件。 18 seen = dict(word_map) # 临时字典，存储的是每个单词的出现次数 19 word_used = 0 20 for j in range(i, i+list_size, word_size): # 从 第i个位置开始，到所有单词总长度的位置，意思是判断这一部分是否满足条件。 21 sub_str = s[j:j+word_size] # 在s中提取相应单词长度的字符串。 22 if sub_str in seen and seen[sub_str] >0: # 如果提出出的字符串在seen字典中，并且相应的值不为0 23 seen[sub_str] -= 1 # 相应字符串的值减一，
24 word_used += 1 # 匹配的数目加一
25 else: 26 break # 如果不满足，直接返回，后面不会存在满足添加的可能。
27 if word_used == num_word: # 相等则表明所有的都匹配完。 28 results.append(i) # 存储下标 29 return results
更多精彩
