【Description】
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 = "wordgoodgoodgoodbestword",
words = ["word","good","best","word"]
Output: []
【Idea】
一个非常之暴力的解法
先用一个字典，统计words中的每个单词及对应的频数，同时用length存储words的长度
遍历给出的s，截取 len(words[0]) * length的长度的字符子串，每四个为一个单词，去字典中查找：
当字典中没有这个单词时，表明该字符串不符合条件，跳入下一遍历；
当字典中有这个单词，该词对应的频数-1， 同时length-1，当length==0且该子串遍历完全，表示该子串符合条件，记录对应最左的index，然后进行下一遍历。
【Solution】
class Solution:
def findSubstring(self, s: str, words):
if s == '' or words == [] or words[0] == '':
return []
dic = {}
output = []
# 初始化标记字典
for w in words:
dic[w] = dic.get(w, 0) + 1
words_len = len(words[0])
for i in range(0, len(s) - len(words[0]) * len(words) + 1):
length = len(words)
import copy
temp_dic = copy.deepcopy(dic)
j = i
while s[j:j + words_len] in words and temp_dic[s[j:j + words_len]] != 0:
temp_dic[s[j:j + words_len]] -= 1
length -= 1
j += words_len
if length == 0:
output.append(i)
return output
