【每日一题】找到字符串中所有字母异位词

题目描述

---

438. 找到字符串中所有字母异位词
给定两个字符串 s 和 p，找到 s 中所有 p 的 异位词 的子串，返回这些子串的起始索引。不考虑答案输出的顺序。

异位词 指由相同字母重排列形成的字符串（包括相同的字符串）。

示例 1:

输入: s = “cbaebabacd”, p = “abc”
输出: [0,6]
解释:
起始索引等于 0 的子串是 “cba”, 它是 “abc” 的异位词。
起始索引等于 6 的子串是 “bac”, 它是 “abc” 的异位词。
示例 2:

输入: s = “abab”, p = “ab”
输出: [0,1,2]
解释:
起始索引等于 0 的子串是 “ab”, 它是 “ab” 的异位词。
起始索引等于 1 的子串是 “ba”, 它是 “ab” 的异位词。
起始索引等于 2 的子串是 “ab”, 它是 “ab” 的异位词。

提示:

1 <= s.length, p.length <= 3 * 104
s 和 p 仅包含小写字母

题解

---

滑动窗口解决，需要注意的是p当中的每个字符可能会重复，如p=aa，对于滑动窗口有效值count的记录判断需要准确。
详情见注释。

class Solution {
public:
    int ss[26];
    int sp[26];
    vector<int> findAnagrams(string s, string p) {
        memset(ss, 0, sizeof ss);
        memset(sp, 0, sizeof sp);
        for (int i = 0; i < p.size(); ++i)
        {
            sp[p[i] - 'a'] ++;
        }
        deque<int> dq;
        int count = 0;
        vector<int> res;
        for (int i = 0; i < s.size(); ++i)
        {
            //入一个s的数，他可能在p当中没有，这种情况count不动,并且也没有必要记录
            //若在p中有，若大于它，则从count 不加加
            //若在p中有，且小于它，则 count++
            if (dq.size() >= p.size())
            {
                char ch = s[i - p.size()];
                if (sp[ch - 'a'] == 0)
                    ;//不能continue，要把末尾元素pop掉
                else if (sp[ch - 'a'] >= ss[ch - 'a'])
                {
                    count--;
                    ss[ch - 'a'] --;
                }
                else if (sp[ch - 'a'] < ss[ch - 'a'])
                {
                    ss[ch - 'a'] --;
                }
                dq.pop_front();
            }
            if (ss[s[i] - 'a'] < sp[s[i] - 'a']) 
                count++;
            dq.push_back(s[i]);

            if (i == 6)
            {
                cout << count << endl;
            }
            ss[s[i] - 'a'] ++;
            if (count == p.size())
            {
                res.push_back(i - p.size() + 1);
            }
        }
        return res;
    }
};
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
39
40
41
42
43
44
45
46
47
48
49
50
51
52

---

end

• 喜欢就收藏
• 认同就点赞
• 支持就关注
• 疑问就评论