SHARE
TWEET

438. Find All Anagrams in a String

goodwish Oct 21st, 2019 67 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. two_pointer, O(n) time.
  2. 简化版的同向双指针, 像 Minimum Window Substring.
  3. window 大小固定, 总是一进一出, 像 strStr II - rolling hash.
  4. .
  5.  
  6. from collections import defaultdict
  7. class Solution:
  8.     def findAnagrams(self, s, p):
  9.         sn, pn = len(s), len(p)
  10.         if pn > sn:
  11.             return []
  12.         r = l = 0
  13.         p_cnt = defaultdict(int)
  14.         s_cnt = defaultdict(int)
  15.         for c in p:
  16.             p_cnt[c] += 1
  17.         tot = 0
  18.         res = []
  19.         for i in range(pn):
  20.             c = s[i]
  21.             if c in p_cnt:
  22.                 if s_cnt[c] < p_cnt[c]:
  23.                     tot += 1
  24.                 s_cnt[c] += 1
  25.        
  26.         for i in range(pn, sn + 1):
  27.             if tot == pn:
  28.                 res.append(i - pn)
  29.             if i == sn:
  30.                 break
  31.             old = s[i - pn]
  32.             new = s[i]
  33.             if old in p_cnt:
  34.                 if 0 < s_cnt[old] <= p_cnt[old]:
  35.                     tot -=1
  36.                 s_cnt[old] -= 1
  37.             if new in p_cnt:
  38.                 if s_cnt[new] < p_cnt[new]:
  39.                     tot += 1
  40.                 s_cnt[new] += 1
  41.        
  42.         return res
  43.  
  44. s, p = \
  45. "bpaa", \
  46. "aa"
  47.  
  48. s = "abddabaff"; p = "ab"
  49.  
  50. o = Solution()
  51. ans = o.findAnagrams(s, p)
  52. print(ans)
RAW Paste Data
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy. OK, I Understand
 
Top