Substring with Concatenation of all words

题目描述

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 = []
        word_length = len(words[0])
        length_s = len(s)
        word_map = {}
        num_word = len(words)

        for word in words:
            if word in word_map:
                word_map[word] += 1 #可能有重复word的，这个沟通好
            else:
                word_map[word] = 1

        cur_start = 0
        while cur_start <= length_s - word_length * num_word: #范围优化
            found = {}
            found_num = 0
            while found_num < num_word:
                w_start = cur_start + found_num * word_length
                cur_w = s[w_start:w_start+word_length]
                if cur_w not in word_map: #不在就跳出
                    break
                if cur_w in found:
                    found[cur_w] += 1
                else:
                    found[cur_w] = 1
                if found[cur_w] > word_map[cur_w]: # 多余了也要跳出
                    break
                found_num += 1 #找到一个，进行下一个~
            if found_num == num_word:
                result.append(cur_start)
            cur_start += 1
        return result

Reference