動機

題目明明已經把same length上粗體了，還看不到…

Problem

You are given a string s and an array of strings words of the same length. Return all starting indices of substring(s) in s that is a concatenation of each word in words exactly once, in any order, and without any intervening characters.

You can return the answer in any order.

 

Example 1:

Input: s = barfoothefoobarman, words = [foo,bar]Output: [0,9]Explanation: Substrings starting at index 0 and 9 are barfoo and foobar respectively.The output order does not matter, returning [9,0] is fine too.

Example 2:

Input: s = wordgoodgoodgoodbestword, words = [word,good,best,word]Output: []

Example 3:

Input: s = barfoofoobarthefoobarman, words = [bar,foo,the]Output: [6,9,12]

 

Constraints:

  • 1 <= s.length <= 104
  • s consists of lower-case English letters.
  • 1 <= words.length <= 5000
  • 1 <= words[i].length <= 30
  • words[i] consists of lower-case English letters.

Sol

如果長度一樣就很簡單

class Solution:
    def findSubstring(self, s: str, words: List[str]) -> List[int]:
        wLen = len(words[0])
        def good(s,ws):
            while ws:
                if s[:wLen] in ws:
                    if ws[s[:wLen]] == 1:
                        del ws[s[:wLen]]
                    else:
                        ws[s[:wLen]] -= 1
                    s = s[wLen:]
                else:
                    return False
            return True

        return [i for i in range(len(s)) if len(s)-i>= wLen*len(words) and good(s[i:],Counter(words))]