438. 找到字符串中所有字母异位词

标签：子串 map ab cur 异位 438 字符串 wanted

 

labuladong 题解思路 难度中等982收藏分享切换为英文接收动态反馈

给定两个字符串 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 仅包含小写字母

 

 

class Solution {
public:
    vector<int> findAnagrams(string s, string p) {
        unordered_map<char,int> wanted_map;
        for(char c:p) {
            wanted_map[c]++;
        }
        int l = 0, r = 0;
        unordered_map<char,int> cur_map;
        int valid = 0;
        vector<int> res;
        while(r < s.size()) {
            char c = s[r];
            if (wanted_map.find(c) != wanted_map.end()) {
                cur_map[c]++;
                if (wanted_map[c]==cur_map[c]) {
                    valid++;
                }
            }
            r++;

            while(r-l >= p.size()) {
                char c2 = s[l];
                if (valid == wanted_map.size()) {
                    res.emplace_back(l);
                }
                // find cur_map, wanted_map 都可以
                if (cur_map.find(c2) != cur_map.end()) {
                    if (cur_map[c2]==wanted_map[c2]) {
                        valid--;
                    }
                    cur_map[c2]--;
                }
                l++;
            }
        }
        return res;
    }
};

 

标签：子串,map,ab,cur,异位,438,字符串,wanted
From： https://www.cnblogs.com/zle1992/p/16609172.html