• 分类：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中的数据

貌似是我有史以来速度最慢的一次