leetcode_438

发表于   |   分类于

Find All Anagrams in a String

题目戳这

题意

给一个字符串s和一个非空串p，求p在s中的所有同字母异序词的下标。比如’abc’和’cba’就是所谓的同字母异序词

解法

这道题目用哈希的思路来解决，外加一个移动窗口，窗口大小为len(p)，每次窗口的内容超过了len(p)，就把最左边的那个字母(刚移出去的)从hash表中移除，注意！在移除某个字符x的时候，我们先mp[x] -= 1,那么此时要判断mp[x]是否为0，为0的话要del mp[x]，因为判断两个hash表是否相同时其实是判断它们的key和value是不是一一对应，而如果mp[x]为0了，x却还是mp的一个key,而事实上这个x已经不能算是mp的key了，所以要删除该key以及对应的value。

代码

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
class Solution(object):
    def findAnagrams(self, s, p):
        """
        :type s: str
        :type p: str
        :rtype: List[int]
        """
        plen = len(p)
        slen = len(s)
        if plen > slen:
            return []
        result = []
        mp1 = {}
        mp2 = {}
        for x in p:
            mp1[x]  = mp1.get(x,0) + 1
        for i in range(slen):
            mp2[s[i]]  = mp2.get(s[i],0) + 1
            if i >= plen:
                mp2[s[i-plen]] -= 1
                if mp2[s[i-plen]] == 0:
                    del mp2[s[i-plen]]
                    
            if mp1 == mp2:
                result.append(i-plen+1)
        
        return result