# 249. Group Shifted Strings

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;
}
};
``````

``````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;
}
};
``````

Github 同步地址：

https://github.com/grandyang/leetcode/issues/249

Group Anagrams

https://leetcode.com/problems/group-shifted-strings/

https://leetcode.com/problems/group-shifted-strings/discuss/67442/My-Concise-JAVA-Solution

https://leetcode.com/problems/group-shifted-strings/discuss/67451/4ms-Easy-C%2B%2B-Solution-with-Explanations

https://leetcode.com/problems/group-shifted-strings/discuss/67452/Concise-10-lines-JAVA-Solution-with-explanation

LeetCode All in One 题目讲解汇总(持续更新中…)

 微信打赏 Venmo 打赏
（欢迎加入博主的知识星球，博主将及时答疑解惑，并分享刷题经验与总结，试运营期间前五十位可享受半价优惠～）

×

Help us with donation