leetcode 30. Substring with Concatenation of All Words 与所有单词相关联的字串滑动窗口法

叁歲伎倆 2022-05-25 10:20 133阅读 0赞

# 题目描述 #

给定一个字符串 s 和一些长度相同的单词 words。在 s 中找出可以恰好串联 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.
    
    Example 1:
    
    Input:
      s = "barfoothefoobarman",
      words = ["foo","bar"]
    Output: [0,9]
    Explanation: Substrings starting at index 0 and 9 are "barfoor" and "foobar" respectively.
    The output order does not matter, returning [9,0] is fine too.
    
    Example 2:
    
    Input:
      s = "wordgoodstudentgoodword",
      words = ["word","student"]
    Output: []

[题目链接][Link 1]

# 解题代码 #

from collections import defaultdict
    
    class Solution:
        def findSubstring(self, s, words):
            """ :type s: str :type words: List[str] :rtype: List[int] """
            res = []
            if len(words) == 0 or len(s) < len(words[0]) * len(words):
                return res
            str_len = len(s)
            word_len = len(words[0])
            total_len = len(words) * word_len
            map_dict = defaultdict(int)
            cur_dict = defaultdict(int)
            for word in words:
                map_dict[word] += 1
    
            for start in range(0, str_len - total_len + 1):
                end = start
                while end < start + total_len:
                    substr = s[end: end + word_len]
                    cur_dict[substr] += 1
                    # 如果当前dict中还有之前的没有的，或者值比至之前的大都终止
                    if cur_dict[substr] > map_dict[substr]:
                        break
                    end += word_len
                if end == start + total_len:
                    res.append(start)
                cur_dict.clear()
            return res

主要还是用滑动窗口法解决问题，有关滑动窗口法的详解，请看[这里][Link 2]  
完整源码在[这里][Link 3]

[Link 1]: https://leetcode.com/problems/substring-with-concatenation-of-all-words/description/
[Link 2]: https://blog.csdn.net/sty945/article/details/79846516
[Link 3]: https://github.com/sty945/leetcodePython/blob/master/Array/30.%20Substring%20with%20Concatenation%20of%20All%20Words.py