30. Substring with Concatenation

【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