Title: Custom Sort String Source: leetcode.com
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”.
Python solution
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 |
''' https://leetcode.com/problems/find-all-anagrams-in-a-string/ ''' class Solution(object): def findAnagrams(self, s, p): """ :type s: str :type p: str :rtype: List[int] """ l = 0 d = {} for c in p: d[c] = d.get(c,0) + 1 l += 1 i = 0 ln = 0 ds = {} res = [] for c in s: if c not in d: ds = {} ln = 0 i += 1 continue ds[c] = ds.get(c, 0) + 1 ln += 1 if ln == l: if d == ds: res.append(i-ln+1) ln -= 1 ds[s[i-ln]] -= 1 if ds[s[i-ln]] == 0: del ds[s[i-ln]] i += 1 return res |
Hello just wanted to give you a quick heads up. The text in your content
seem to be running off the screen in Opera. I’m not sure if this is a format issue or something to do with
internet browser compatibility but I figured I’d post to let you
know. The style and design look great though! Hope
you get the issue solved soon. Cheers
Thank you for notifying. The issue should be fixed now.
Thanks again!