雜湊與字串實戰：5 題從讀題推導到最優解（LC 242/49/271/560/128）

def isAnagram(s, t):
    if len(s) != len(t):
        return False
    count = {}
    for c in s:
        count[c] = count.get(c, 0) + 1
    for c in t:
        if count.get(c, 0) == 0:
            return False
        count[c] -= 1
    return True

bool isAnagram(string s, string t) {
    if (s.size() != t.size()) return false;
    int count[26] = {0};
    for (char c : s) count[c - 'a']++;
    for (char c : t) {
        if (--count[c - 'a'] < 0) return false;
    }
    return true;
}

from collections import defaultdict

def groupAnagrams(strs):
    groups = defaultdict(list)
    for s in strs:
        count = [0] * 26
        for c in s:
            count[ord(c) - ord('a')] += 1
        groups[tuple(count)].append(s)   # char-count as key
    return list(groups.values())

vector<vector<string>> groupAnagrams(vector<string>& strs) {
    unordered_map<string, vector<string>> groups;
    for (auto& s : strs) {
        string key = s;
        sort(key.begin(), key.end());    // sorted string as key
        groups[key].push_back(s);
    }
    vector<vector<string>> res;
    for (auto& [k, v] : groups) res.push_back(v);
    return res;
}

def encode(strs):
    return ''.join(f'{len(s)}#{s}' for s in strs)

def decode(s):
    res, i = [], 0
    while i < len(s):
        j = i
        while s[j] != '#':            # read the length digits
            j += 1
        length = int(s[i:j])
        res.append(s[j + 1: j + 1 + length])
        i = j + 1 + length
    return res

string encode(vector<string>& strs) {
    string res;
    for (auto& s : strs) res += to_string(s.size()) + "#" + s;
    return res;
}

vector<string> decode(string s) {
    vector<string> res;
    int i = 0, n = s.size();
    while (i < n) {
        int j = i;
        while (s[j] != '#') j++;       // read the length digits
        int len = stoi(s.substr(i, j - i));
        res.push_back(s.substr(j + 1, len));
        i = j + 1 + len;
    }
    return res;
}

from collections import defaultdict

def subarraySum(nums, k):
    count = defaultdict(int)
    count[0] = 1                  # empty prefix: enables subarrays from index 0
    prefix = res = 0
    for n in nums:
        prefix += n
        res += count[prefix - k]  # how many earlier prefixes = prefix - k
        count[prefix] += 1
    return res

int subarraySum(vector<int>& nums, int k) {
    unordered_map<int, int> count;
    count[0] = 1;                 // empty prefix
    int prefix = 0, res = 0;
    for (int n : nums) {
        prefix += n;
        auto it = count.find(prefix - k);
        if (it != count.end()) res += it->second;
        count[prefix]++;
    }
    return res;
}

def longestConsecutive(nums):
    num_set = set(nums)
    longest = 0
    for n in num_set:
        if n - 1 not in num_set:        # n is the start of a sequence
            length = 1
            while n + length in num_set:
                length += 1
            longest = max(longest, length)
    return longest

int longestConsecutive(vector<int>& nums) {
    unordered_set<int> s(nums.begin(), nums.end());
    int longest = 0;
    for (int n : s) {
        if (s.find(n - 1) == s.end()) {     // n is a sequence start
            int length = 1;
            while (s.find(n + length) != s.end()) length++;
            longest = max(longest, length);
        }
    }
    return longest;
}