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.

For example, given:
s: “barfoothefoobarman”
words: [“foo”, “bar”]

You should return the indices: [0,9].
(order does not matter).

题意

实现字符串匹配,我做的时间复杂度比较高，勉强accepted，暂时还没有看懂比较简单的代码（后期可以再看看）

Python实现

class Solution(object):
    def findSubstring(self, s,words):
        """
        :type s: str
        :type words: List[str]
        :rtype: List[int]
        """
        word_dict={}
        index_list=[]
        for word in words:
            if word not in word_dict.keys():
                word_dict[word]=0
            word_dict[word]+=1
        word_length=len(words[0])
        s_length=len(s)
        
        for i in range(s_length-(word_length*len(words))+1):
            k=i
            word_dict_cp={}
            num=0
            while k+word_length<=s_length:
                word=s[k:k+word_length]
                if word not in word_dict:break
                if word not in word_dict_cp:word_dict_cp[word]=0
                word_dict_cp[word]+=1
                if word_dict_cp[word]>word_dict[word]:break
                num+=1
                k=k+word_length
                if num==len(words):
                    index_list.append(i)
                    break

        return index_list