30. 串联所有单词的子串

exiaohu 于 2022-06-23 发布

题目链接:30. 串联所有单词的子串

给定的单词长度相同,设它们的长度是 $k$,元素数目为 $n$,那么一个长度为 $nk$ 的字符串是否能由 $words$ 组成,可以用 Counter 判断。

遍历所有可能的下标,判断即可。

from collections import Counter
from typing import List


class Solution:
    def findSubstring(self, s: str, words: List[str]) -> List[int]:
        n_words, l_word, words_counter = len(words), len(words[0]), Counter(words)

        return [i - n_words * l_word for i in range(n_words * l_word, len(s) + 1)
                if words_counter == Counter(s[j: j + l_word] for j in range(i - n_words * l_word, i, l_word))]