Skip to content

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
29
class Solution {
 public:
  vector<vector<string>> groupStrings(vector<string>& strings) {
    vector<vector<string>> ans;
    unordered_map<string, vector<string>> keyToStrings;

    for (const string& s : strings)
      keyToStrings[getKey(s)].push_back(s);

    for (const auto& [_, strings] : keyToStrings)
      ans.push_back(strings);

    return ans;
  }

 private:
  // Returns the key of 's' by pairwise calculation of differences.
  // e.g. getKey("abc") -> "1,1" 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
23
class Solution {
  public List<List<String>> groupStrings(String[] strings) {
    Map<String, List<String>> keyToStrings = new HashMap<>();

    for (final String s : strings)
      keyToStrings.computeIfAbsent(getKey(s), k -> new ArrayList<>()).add(s);

    return new ArrayList<>(keyToStrings.values());
  }

  // Returns the key of 's' by pairwise calculation of differences.
  // e.g. getKey("abc") -> "1,1" 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
19
20
21
class Solution:
  def groupStrings(self, strings: List[str]) -> List[List[str]]:
    keyToStrings = collections.defaultdict(list)

    def getKey(s: str) -> str:
      """
      Returns the key of 's' by pairwise calculation of differences.
      e.g. getKey("abc") -> "1,1" because diff(a, b) = 1 and diff(b, c) = 1.
      """
      diffs = []

      for i in range(1, len(s)):
        diff = (ord(s[i]) - ord(s[i - 1]) + 26) % 26
        diffs.append(str(diff))

      return ','.join(diffs)

    for s in strings:
      keyToStrings[getKey(s)].append(s)

    return keyToStrings.values()