Given a string, we can "shift" each of its letter to its successive letter, for example: "abc" -> "bcd". We can keep "shifting" which forms the sequence:
"abc" -> "bcd" -> ... -> "xyz"
Given a list of strings which contains only lowercase alphabets, group all strings that belong to the same shifting sequence.
For example, given: ["abc", "bcd", "acef", "xyz", "az", "ba", "a", "z"],
Return:
[ ["abc","bcd","xyz"], ["az","ba"], ["acef"], ["a","z"] ]
Note: For the return value, each inner list's elements must follow the lexicographic order.
解法一：
// Correct but complicated class Solution { public: vector<vector<string>> groupStrings(vector<string>& strings) { vector<vector<string> > res; unordered_map<string, multiset<string>> m; for (auto a : strings) { bool b = false; for (auto it = m.begin(); it != m.end(); ++it) { if (isShifted(it->first, a)) { it->second.insert(a); b = true; } } if (!b) m[a] = {a}; } for (auto it = m.begin(); it != m.end(); ++it) { res.push_back(vector<string>(it->second.begin(), it->second.end())); } return res; } bool isShifted(string s1, string s2) { if (s1.size() != s2.size()) return false; int diff = (s1[0] + 26 - s2[0]) % 26; for (int i = 1; i < s1.size(); ++i) { if ((s1[i] + 26 - s2[i]) % 26 != diff) return false; } return true; } };
上面那个方法挺复杂的，其实有更好的方法，网友的智慧无穷啊，上面那个方法的不高效之处在于对于每个遍历到的字符串，都要和哈希表中所有的关键字都比较一次，而其实我们可以更加巧妙的利用偏移字符串的特点，那就是字符串的每个字母和首字符的相对距离都是相等的，比如abc和efg互为偏移，对于abc来说，b和a的距离是1，c和a的距离是2，对于efg来说，f和e的距离是1，g和e的距离是2。再来看一个例子，az和yx，z和a的距离是25，x和y的距离也是25(直接相减是-1，这就是要加26然后取余的原因)，那么这样的话，所有互为偏移的字符串都有个unique的距离差，我们根据这个来建立映射就可以很好的进行单词分组了，这个思路真实太赞了，参见代码如下：
解法二：
class Solution { public: vector<vector<string>> groupStrings(vector<string>& strings) { vector<vector<string> > res; unordered_map<string, multiset<string>> m; for (auto a : strings) { string t = ""; for (char c : a) { t += to_string((c + 26 - a[0]) % 26) + ","; } m[t].insert(a); } for (auto it = m.begin(); it != m.end(); ++it) { res.push_back(vector<string>(it->second.begin(), it->second.end())); } return res; } };
本文转自博客园Grandyang的博客，原文链接：群组偏移字符串[LeetCode] Group Shifted Strings ，如需转载请自行联系原博主。
