LeetCode Q249: 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"]
]

Solution:
Look at the difference between each character and use all differences of a string as key in a hash map.

	class Solution {
	public:
	vector<vector<string>> groupStrings(vector<string>& strings) {
	unordered_map<string ,int> myMap;
	vector<vector<string> > res;
	int idx=0;
	for(int i=0; i<strings.size(); i++){
	string str = strings[i];
	string key("0");
	for(int j=1; j<str.length(); j++){
	int tmp = (26+str[j]-str[j-1])%26;
	key = key + string("_") + to_string(tmp);
	}
	unordered_map<string, int>::const_iterator it = myMap.find(key);
	if(it==myMap.end()){
	vector<string> newStr;
	newStr.push_back(str);
	res.push_back(newStr);
	myMap[key] = idx;
	idx++;
	}else
	res[myMap[key]].push_back(str);
	}
	for(int i=0; i<res.size(); i++)
	sort(res[i].begin(), res[i].end());
	return res;
	}
	};

view raw Q249GourpShiftedStrings.cpp hosted with ❤ by GitHub

Round 2 solution:

	class Solution {
	public:
	vector<vector<string>> groupStrings(vector<string>& strings) {
	unordered_map<string, vector<string> > myHash;
	vector<vector<string> > res;
	for(int i=0; i<strings.size(); i++){
	string str = strings[i];
	int dist = str[0]-'a';
	for(int j=0; j<str.length(); j++)
	str[j] = 'a'+(str[j]-'a'+26-dist)%26;
	auto it = myHash.find(str);
	if(it==myHash.end()){
	vector<string> v(1, strings[i]);
	myHash[str]=v;
	}else
	myHash[str].push_back(strings[i]);
	}
	for(auto it = myHash.begin(); it!=myHash.end(); it++)
	res.push_back(it->second);
	return res;
	}
	};

view raw Q249Rnd2.cpp hosted with ❤ by GitHub