首页 > 代码库 > Leetcode 438. Find All Anagrams in s String
Leetcode 438. Find All Anagrams in s String
Given a string s and a non-empty string p, find all the start indices of p‘s anagrams in s.
Strings consists of lowercase English letters only and the length of both strings s and p will not be larger than 20,100.
The order of output does not matter.
Example 1:
Input: s: "cbaebabacd" p: "abc" Output: [0, 6] Explanation: The substring with start index = 0 is "cba", which is an anagram of "abc". The substring with start index = 6 is "bac", which is an anagram of "abc".
Example 2:
Input: s: "abab" p: "ab" Output: [0, 1, 2] Explanation: The substring with start index = 0 is "ab", which is an anagram of "ab". The substring with start index = 1 is "ba", which is an anagram of "ab". The substring with start index = 2 is "ab", which is an anagram of "ab".
思路:使用滑动窗口的思想
s = cbaebabacd
p = abc
w = [cb]
w+a = [cba],如果counter之后等于counter(p), 输出头index。在remove 第一个字母c的时候,注意这是counter c的value是不是1。如果是1的话,直接remove。不是1的话,减1。
1 from collections import Counter 2 3 class Solution(object): 4 def findAnagrams(self, s, p): 5 """ 6 :type s: str 7 :type p: str 8 :rtype: List[int] 9 """ 10 size = len(p) 11 n = len(s) 12 pCounter = Counter(p) 13 sCounter = Counter(s[:size-1]) 14 15 ans = [] 16 17 for i in range(size-1,n): 18 sCounter[s[i]] += 1 19 if sCounter == pCounter: 20 ans.append(i-size+1) 21 if sCounter[s[i-size+1]] == 1: 22 del sCounter[s[i-size+1]] 23 else: 24 sCounter[s[i-size+1]] -= 1 25 return ans
Leetcode 438. Find All Anagrams in s String
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。