249. Group Shifted Strings

O(C) time O(C) space
normalize每个单词存到hashmap里

class Solution {
public:
    vector<vector<string>> groupStrings(vector<string>& strings) {
        unordered_map<string, vector<string>> m;
        for (const auto &s : strings) {
            m[norm(s)].push_back(s);
        }
        vector<vector<string>> res;
        for (auto &&[_, v] : m) {
            res.push_back(move(v));
        }
        return res;
    }

    string norm(string s) { // 返回以ASCII码0为基准的字符串
        int offset = 26 - s[0]; // 不关心'a'，只关心每个字符和s[0]的offset
        for (auto &&c : s) {
            c = (c + offset) % 26;
        }
        return s;
    }
};

class Solution {
public:
    vector<vector<string>> groupStrings(vector<string>& strings) {
        unordered_map<string, vector<string>> m;
        for (const auto &s : strings) {
            m[norm(s)].push_back(s);
        }
        vector<vector<string>> res;
        for (auto &&[_, v] : m) {
            res.push_back(move(v)); // 转成右值直接move过去避免copy
        }
        return res;
    }

    string norm(string s) { // 返回值并不需要是一个正常的纯英文可读字符串
        int offset = 26 + 'a' - s[0]; // 这里假设以ASCII码0为基准 最后所有的'a'都变成0
        for (auto &&c : s) {
            c = (c - 'a' + offset) % 26; // 减'a'以后以字符0为基准 实际上因为是Galois Field不减'a'也行 但是不好描述
        }
        return s;
    }
};

class Solution {
public:
    vector<vector<string>> groupStrings(vector<string>& strings) {
        unordered_map<string, vector<int>> m; // 存下标就行，最后整理再放字符串
        int n = strings.size();
        for (int i = 0; i < n; ++i) {
            m[norm(strings[i])].push_back(i);
        }
        vector<vector<string>> res;
        for (const auto &[_, v] : m) {
            res.push_back({});
            for (int i : v) {
                res.back().push_back(strings[i]);
            }
        }
        return res;
    }

    string norm(string s) {
        int offset = 26 + 'a' - s[0];
        for (char &c : s) {
            c = (c + offset) % 26;
        }
        return s;
    }
};

class Solution {
public:
    vector<vector<string>> groupStrings(vector<string>& strings) {
        unordered_map<string, vector<string>> m;
        for (const auto &s : strings) {
            m[norm(s)].push_back(s);
        }
        vector<vector<string>> res;
        for (auto &&[_, v] : m) {
            res.push_back({});
            res.back().swap(v);
        }
        return res;
    }

    string norm(string s) { // 输出以'a'为基准的真正可读字符串
        int offset = 'a' - s[0];
        for (auto &&c : s) {
            auto t = c + offset;
            if (t < 'a') {
                c = 'a' + (t - 'a') + 26;
            } else {
                c = t;
            }
        }
        return s;
    }
};