本文共 2461 字,大约阅读时间需要 8 分钟。
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".
找到一个字符串里所有的字谜
方法一:295msfrom collections import Counterclass Solution(object): def findAnagrams(self, s, p): """ :type s: str :type p: str :rtype: List[int] """ ans = [] ls, lp = len(s), len(p) count = lp cp = collections.Counter(p) for i in range(ls): if cp[s[i]] >= 1: count -= 1 cp[s[i]] -= 1 if i >= lp: if cp[s[i-lp]] >= 0: count += 1 cp[s[i-lp]] += 1 if count == 0: ans.append(i - lp + 1) return ans
方法二:146ms
from collections import defaultdictclass Solution(object): def findAnagrams(self, s, p): """ :type s: str :type p: str :rtype: List[int] """ res = [] if not p or not s: return res lenP = len(p) lenS = len(s) if lenS < lenP: return res hP = defaultdict(int) for ch in p: hP[ch] += 1 count = len(hP.keys()) for i in xrange(lenP): ch = s[i] if ch in hP: hP[ch] -= 1 if hP[ch] == 0: count -= 1 if count == 0: res.append(0) left = 0 right = lenP while right < lenS: ch = s[right] if ch in hP: hP[ch] -= 1 if hP[ch] == 0: count -= 1 ch = s[left] if ch in hP: hP[ch] += 1 if hP[ch] == 1: count += 1 left += 1 right += 1 if count == 0: res.append(left) return res
转载地址:http://lgcrj.baihongyu.com/