Home
Algorithms Data Structures Interview Experiences
Amazon Google Facebook Microsoft Apple Netflix
Play 2048 How to

LeetCode Solutions

249. Group Shifted Strings

Time: $O(\Sigma |\texttt{strings[i]}|)$

Space: $O(\Sigma |\texttt{strings[i]}|)$

			


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:
  // "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;
  }
};




			


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());
  }

  // "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();
  }
}




			


class Solution:
  def groupStrings(self, strings: List[str]) -> List[List[str]]:
    keyToStrings = 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()