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

🔗 https://leetcode.cn/problems/find-all-anagrams-in-a-string

题目

• 给出两个字符串 s 和 p，找到 s 的子串是 p 的异位词，返回这些子串的开始索引
• 异位词表示两个字符串的字母排序后相同

思路

• 以 p.size() 为窗口大小，滑动 s，判断这过程中，s 的子串和 p 是否为异位词
• 异位词的判断在题目 49. 字母异位词分组 中使用的 hash_map，这里因为字母仅有 26 位且都是小写字母，用长度为 26 的一位数据进行编码

代码

class Solution {
public:
    bool is_equal(vector<int>& a, vector<int>& b) {
        for (int i = 0; i < 26; i++) {
            if (a[i] != b[i]) return false;
        }
        return true;
    }
    vector<int> findAnagrams(string s, string p) {    
        vector<int> ans;
        if (s.size() < p.size()) return ans;
        vector<int> p_count(26);
        for (char& ch : p) {
            p_count[ch - 'a']++;
        }
        vector<int> s_count(26);
        for (int i = 0; i < p.size()-1; i++) {
            char ch = s[i];
            s_count[ch - 'a']++;
        }
        for (int i = 0; i < s.size() - p.size() + 1; i++) {
            char ch = s[i + p.size()-1];
            s_count[ch - 'a']++;
            if (is_equal(p_count, s_count)) ans.push_back(i);
            s_count[s[i] - 'a']--;
        }
        return ans;
        
    }
};

原文地址：https://blog.csdn.net/weixin_42383726/article/details/143948965

免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！