249. Group Shifted Strings - cocoder39/coco39_LC GitHub Wiki

249. Group Shifted Strings

Notes 2020:

class Solution:
    def groupStrings(self, strings: List[str]) -> List[List[str]]:
        groups = collections.defaultdict(list)
        for s in strings:
            key = tuple([(ord(ch) - ord(s[0])) % 26 for ch in s])
            groups[key].append(s)
        return list(groups.values())

approach below has a bug: eg key1 = (1, 11) and key2 = (11, 1) but key1 and key2 will be taken as identical

class Solution:
    def groupStrings(self, strings: List[str]) -> List[List[str]]:
        groups = collections.defaultdict(list)
        for string in strings:
            key = []
            for i in range(1, len(string)):
                diff = (ord(string[i]) - ord(string[i-1]) + 26) % 26
                key.append(chr(diff))
            groups[''.join(key)].append(string)
        return list(groups.values())

==============================================================

idea: encode the string to a basic mode which starts with 'a'. Then map strings with same base mode into a multiset

the most essential part is

char c = s[i] - diff;
s[i] = c < 'a' ? c + 26 : c;

if 'z' is mapped to 'a', then 'a' will be mapped to 'b'

class Solution {
public:
    vector<vector<string>> groupStrings(vector<string>& strings) {
        unordered_map<string, multiset<string>> map;
        for (auto &str : strings) {
            string base = getBase(str);
            map[base].insert(str);
        }
        
        vector<vector<string>> res;
        for (auto &m : map) {
            vector<string> tmp;
            for (auto &str : m.second) {
                tmp.push_back(str);
            }
            res.push_back(tmp);
        }
        return res;
    }
private:
    string getBase(string s) {
        int diff = s[0] - 'a';
        if (diff == 0) {
            return s;
        }
        
        s[0] = 'a';
        for (int i = 1; i < s.length(); i++) {
            char c = s[i] - diff;
            s[i] = c < 'a' ? c + 26 : c;
        }
        return s;
    }
};
⚠️ **GitHub.com Fallback** ⚠️