题目浅析

  • 想查看原题可以点击题目链接。

  • 简单地说，就是给了两个字符串，求一个字符串的异位词在另一个字符串的所有起始索引，所谓的异位词，就是把字符串中的字母重新排列所得的字符串。

思路分享

  • 与上一题【Leetcode Daily】567字符串的排列十分相似，区别仅在于本题要把所有“异位词”的起始索引都记下，所有只用改几行代码就能 ac 了。

  • 不过这题灵茶山艾府有题解，姑且加一段解析他的题解好力。灵茶山艾府的定长滑动窗口解法，是采用两个哈希表，分别记录两边的字符串的各字母个数，滑动窗口的内容也只要维护其中一个哈希表的进出，至于判断异位词的方法，就是简单粗暴地直接用等号判断（unordered_map重载过==了罢）。私以为，实现更为符合直觉，不过论效率应该不如陆爻齐的解法，空间上少一个哈希表，时间上差不多罢。

代码解答（强烈建议自行解答后再看）

  • 陆爻齐的解法
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
class Solution {
public:
    vector<int> findAnagrams(string s, string p) {
        vector<int> rec(26, 0);
        int count_char = 0;
        for (const char a : p) {
            rec[a-'a']++;
            if (rec[a-'a']==1) count_char++;
        }

        int n = s.length();
        int win = p.length();
        vector<int> res;
        for (int i = 0; i < n; i++) {
            if (rec[s[i]-'a']--==1) count_char--;

            if (i < win-1) continue;

            if (count_char==0) res.push_back(i-win+1);

            if (rec[s[i-win+1]-'a']++==0) count_char++;
        }
        return res;
    }
};