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].

解题方法

Solution

class Solution(object):
    def findSubstring(self, s, words):
        """
        :type s: str
        :type words: List[str]
        :rtype: List[int]
        """
        if not s or not words:
            return
        result = []

        wMap = {}
        # word出现的次数也要统计
        for word in words:
            if word in wMap:
                wMap[word] += 1
            else:
                wMap[word] = 1
        found = {}

        wLength = len(words[0])
        numWord = len(words)

        left = 0
        for left in range(len(s) - wLength * numWord + 1):
            found = {}
            k = 0
            # 最长check numWord个word的长度
            while k < numWord:
                wStart = left + k * wLength
                word = s[wStart: wStart + wLength]
                if word not in wMap:
                    # this word is not in the list
                    break
                else:
                    if word in found:
                        found[word] += 1
                    else:
                        found[word] = 1
                    # 如果次数多于原来的，说明不对了就break
                    if found[word] > wMap[word]:
                        break
                k += 1
            if k == numWord:
                result.append(left)

        return result

Reference