# 249. Group Shifted Strings

• Time: $O(\Sigma |\texttt{strings[i]}|)$
• Space: $O(\Sigma |\texttt{strings[i]}|)$
  1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 class Solution { public: vector> groupStrings(vector& strings) { vector> ans; unordered_map> keyToStrings; for (const string& s : strings) keyToStrings[getKey(s)].push_back(s); for (const auto& [_, strings] : keyToStrings) ans.push_back(strings); return ans; } private: // "abc" -> "11" because diff(a, b) = 1 and diff(b, c) = 1 string getKey(const string& s) { string key; for (int i = 1; i < s.length(); ++i) { const int diff = (s[i] - s[i - 1] + 26) % 26; key += to_string(diff) + ","; } return key; } }; 
  1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 class Solution { public List> groupStrings(String[] strings) { Map> keyToStrings = new HashMap<>(); for (final String s : strings) keyToStrings.computeIfAbsent(getKey(s), k -> new ArrayList<>()).add(s); return new ArrayList<>(keyToStrings.values()); } // "abc" -> "11" because diff(a, b) = 1 and diff(b, c) = 1 private String getKey(final String s) { StringBuilder sb = new StringBuilder(); for (int i = 1; i < s.length(); ++i) { final int diff = (s.charAt(i) - s.charAt(i - 1) + 26) % 26; sb.append(diff).append(","); } return sb.toString(); } } 
  1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 class Solution: def groupStrings(self, strings: List[str]) -> List[List[str]]: keyToStrings = collections.defaultdict(list) # 'abc' . '11' because diff(a, b) = 1 and diff(b, c) = 1 def getKey(s: str) -> str: key = '' for i in range(1, len(s)): diff = (ord(s[i]) - ord(s[i - 1]) + 26) % 26 key += str(diff) + ',' return key for s in strings: keyToStrings[getKey(s)].append(s) return keyToStrings.values()