• 分類：HashTable

• 考察知識點：HashTable 數(shù)組遍歷

• 最優(yōu)解時間復(fù)雜度：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中去，然后在每次循環(huán)的時候弄一個dict_copy,再循環(huán)判斷dict_copy中的數(shù)據(jù)

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