LeetCode 249. Group Shifted Strings

 249. Group Shifted Strings

We can shift a string by shifting each of its letters to its successive letter.

• For example, "abc" can be shifted to be "bcd".

We can keep shifting the string to form a sequence.

• For example, we can keep shifting "abc" to form the sequence: "abc" -> "bcd" -> ... -> "xyz".

Given an array of strings strings, group all strings[i] that belong to the same shifting sequence. You may return the answer in any order.

 

Example 1:

Input: strings = ["abc","bcd","acef","xyz","az","ba","a","z"]
Output: [["acef"],["a","z"],["abc","bcd","xyz"],["az","ba"]]

Example 2:

Input: strings = ["a"]
Output: [["a"]]

 

Constraints:

• 1 <= strings.length <= 200
• 1 <= strings[i].length <= 50
• strings[i] consists of lowercase English letters.

	class Solution {
	public:
	char shiftLetter(char letter, int shift) {
	// if circular
	return (letter - shift + 26) % 26 + 'a';
	}
	// Create a hash value
	string getHash(string& s) {
	// Calculate the number of shifts to make the first character to be 'a'
	int shift = s[0];
	string hashKey;
	for (char letter : s) {
	hashKey += shiftLetter(letter, shift);
	}
	return hashKey;
	}
	vector<vector<string>> groupStrings(vector<string>& strings) {
	unordered_map<string, vector<string>> mapHashToList;
	// Create a hash_value (hashKey) for each string and append the string
	// to the list of hash values i.e. mapHashToList["abc"] = ["abc", "bcd"]
	for (string str : strings) {
	string hashKey = getHash(str);
	mapHashToList[hashKey].push_back(str);
	}
	// Iterate over the map, and add the values to groups
	vector<vector<string>> groups;
	for (auto it : mapHashToList) {
	groups.push_back(it.second);
	}
	return groups;
	}
	};

view raw 249. Group Shifted Strings.cpp hosted with ❤ by GitHub