249. Group Shifted Strings

The intuition is to create a pattern for each string and use the pattern as key in hash table. The value is a string vector that contains all strings follow the same pattern. Then the problem becomes how to create the pattern. The naive way is to use "a" + diff. Since the diff can be negative (e.g. "ba" and "az"), we should 26 to it.

1:  class Solution {  
2:  public:  
3:    vector<vector<string>> groupStrings(vector<string>& strings) {  
4:      unordered_map<string, vector<string>> mp;  
5:      for (string s : strings) {  
6:        mp[pattern(s)].push_back(s);  
7:      }  
8:      vector<vector<string>> res;  
9:      for (auto it : mp) {  
10:        vector<string> r = it.second;  
11:        sort(r.begin(), r.end());  
12:        res.push_back(r);  
13:      }  
14:      return res;  
15:    }  
16:    string pattern(string &s) {  
17:      string p = "";  
18:      for (int i = 1; i < s.size(); i++) {  
19:        int diff = s[i]-s[i-1];  
20:        if (diff < 0) diff += 26;  
21:        p += "a" + to_string(diff);  
22:      }  
23:      return p;  
24:    }  
25:  };