Uriel's Corner

Research Associate @ Harvard University / Research Interests: Computer Vision, Biomedical Image Analysis, Machine Learning
posts - 0, comments - 50, trackbacks - 0, articles - 594
给出两个字符串p和s,问p的某种排列是否是s的子串,如果存在,输出所有匹配的位置。类似第567题(http://www.cppblog.com/Uriel/articles/229660.html)
先用Counter计算p各个字符的出现次数,然后用sliding window,s出现在sliding window中的字符对应的Counter减1,发现某位置sliding window让Counter中所有计数归零时记录位置


 1 #438
 2 #Runtime: 371 ms (Beats 12.21%)
 3 #Memory: 14.6 MB (Beats 29.63%)
 4 
 5 class Solution(object):
 6     def findAnagrams(self, s, p):
 7         """
 8         :type s: str
 9         :type p: str
10         :rtype: List[int]
11         """
12         cnt_p = Counter(p)
13         l = len(p)
14         ans = []
15         for i in range(len(s)):
16             if s[i] in cnt_p:
17                 cnt_p[s[i]] -= 1
18             if i >= l and s[i-l] in cnt_p:
19                 cnt_p[s[i-l]] += 1
20             if all([cnt_p[j] == 0 for j in cnt_p]):
21                 ans.append(i - l + 1)
22         return ans

只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理