# [leetcode] Group Shifted Strings

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.

Circle shift.

Shift the string to a base state whose first letter is ‘a’. Use this base string as key, and the original string as value. Insert them into hashmap.

```class Solution {
public:
vector<vector<string>> groupStrings(vector<string>& strings) {
vector<vector<string>> ans;
unordered_map<string, vector<string>> map;
for(auto it = strings.begin(); it != strings.end(); it++){
string base = *it;
if(base.size() == 0) continue;
int offset = base - 'a';
for(int i = 0; i < base.size(); i++){
base[i] = base[i] - offset;
if(base[i] < 'a') base[i] += 26;
}
if(map.find(base) == map.end()){
// new base string
vector<string> element;
element.push_back(*it);
map[base] = element;
}else{
// append *it to base string vector
map[base].push_back(*it);
}
}
for(auto it = map.begin(); it != map.end(); it++){
auto vstr = it->second;
sort(vstr.begin(), vstr.end());
ans.push_back(vstr);
}
return ans;
}
};```

This site uses Akismet to reduce spam. Learn how your comment data is processed.