49/438-字母异位词分组

LeetCode 49. Group Anagrams

LeetCode-49

Given an array of strings strs, group the anagrams together. You can return the answer in any order.

An Anagram is a word or phrase formed by rearranging the letters of a different word or phrase, typically using all the original letters exactly once.

Example 1:

Input: strs = ["eat","tea","tan","ate","nat","bat"]
Output: [["bat"],["nat","tan"],["ate","eat","tea"]]

method

同一组内的单词排序后肯定是一样的，所以用排序后的字符串作为哈希表的键，有相同键的就分为一组

vector<vector<string>> groupAnagrams(vector<string>& strs) {
    unordered_map<string, vector<string>> hash;
    for (auto str : strs) {
        string key = str;
        sort(key.begin(), key.end());   // 排序
        hash[key].push_back(str);   // 相同键的放一起
    }
    vector<vector<string>> res;
    for (auto t : hash) {
        res.push_back(t.second);    // t.first是排序的键，t.second是对应的字符串数组
    }
    return res;
}

---

LeetCode 438. Find All Anagrams in a String

LeetCode-438

Given two strings s and p, return an array of all the start indices of p‘s anagrams in s. You may return the answer in any order.

An Anagram is a word or phrase formed by rearranging the letters of a different word or phrase, typically using all the original letters exactly once.

Example 1:

Input: s = "cbaebabacd", p = "abc"
Output: [0,6]
Explanation:
The substring with start index = 0 is "cba", which is an anagram of "abc".
The substring with start index = 6 is "bac", which is an anagram of "abc".

method：滑动窗口

维护一个长度为pLen的窗口，每次比较窗口内的元素的出现次数与p的元素的出现次数是否相同

窗口右端点是i，则左端点是i-pLen+1，这样才满足长度为pLen

vector<int> findAnagrams(string s, string p) {
    int sLen = s.size(), pLen = p.size();
    if (sLen < pLen) return {};
    vector<int> sCount(26); // 用于统计的哈希表
    vector<int> pCount(26);
    vector<int> res;
    for (int i = 0; i < pLen; i++) {
        sCount[s[i] - 'a']++;   // 统计前面pLen个字符
        pCount[p[i] - 'a']++;
    }
    if (sCount == pCount) res.push_back(0);
    for (int i = pLen; i < sLen; i++) {
        sCount[s[i] - 'a']++;       // 窗口移动，去掉i位置的元素
        sCount[s[i - pLen] - 'a']--;    // 加上i+pLen位置的元素，i+pLen<sLen --> i<sLen-pLen
        if (sCount == pCount) res.push_back(i - pLen + 1);  // [i-pLen+1, i]
    }
    return res;
}