題目描述

給定一個(gè)字符串 s 和一些長(zhǎng)度相同的單詞 words。在 s 中找出可以恰好串聯(lián) 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: []

題目鏈接

解題代碼

from collections import defaultdictclass 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 resstr_len = len(s)word_len = len(words[0])total_len = len(words) * word_lenmap_dict = defaultdict(int)cur_dict = defaultdict(int)for word in words:map_dict[word] += 1for start in range(0, str_len - total_len + 1):end = startwhile end < start + total_len:substr = s[end: end + word_len]cur_dict[substr] += 1# 如果當(dāng)前dict中還有之前的沒(méi)有的，或者值比至之前的大都終止if cur_dict[substr] > map_dict[substr]:breakend += word_lenif end == start + total_len:res.append(start)cur_dict.clear()return res

主要還是用滑動(dòng)窗口法解決問(wèn)題，有關(guān)滑動(dòng)窗口法的詳解，請(qǐng)看這里
完整源碼在這里

總結(jié)

以上是生活随笔為你收集整理的leetcode 30. Substring with Concatenation of All Words 与所有单词相关联的字串 滑动窗口法的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

如果覺(jué)得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。