Question

249. Group Shifted Strings

中文文档

Description

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.

Solutions

Solution 1

class Solution:
  def groupStrings(self, strings: List[str]) -> List[List[str]]:
    mp = defaultdict(list)
    for s in strings:
      t = []
      diff = ord(s[0]) - ord('a')
      for c in s:
        d = ord(c) - diff
        if d < ord('a'):
          d += 26
        t.append(chr(d))
      k = ''.join(t)
      mp[k].append(s)
    return list(mp.values())

class Solution {
  public List<List<String>> groupStrings(String[] strings) {
    Map<String, List<String>> mp = new HashMap<>();
    for (String s : strings) {
      int diff = s.charAt(0) - 'a';
      char[] t = s.toCharArray();
      for (int i = 0; i < t.length; ++i) {
        char d = (char) (t[i] - diff);
        if (d < 'a') {
          d += 26;
        }
        t[i] = d;
      }
      String key = new String(t);
      mp.computeIfAbsent(key, k -> new ArrayList<>()).add(s);
    }
    return new ArrayList<>(mp.values());
  }
}

class Solution {
public:
  vector<vector<string>> groupStrings(vector<string>& strings) {
    unordered_map<string, vector<string>> mp;
    for (auto& s : strings) {
      int diff = s[0] - 'a';
      string t = s;
      for (int i = 0; i < t.size(); ++i) {
        char d = t[i] - diff;
        if (d < 'a') d += 26;
        t[i] = d;
      }
      cout << t << endl;
      mp[t].push_back(s);
    }
    vector<vector<string>> ans;
    for (auto& e : mp)
      ans.push_back(e.second);
    return ans;
  }
};

func groupStrings(strings []string) [][]string {
  mp := make(map[string][]string)
  for _, s := range strings {
    k := ""
    for i := range s {
      k += string((s[i]-s[0]+26)%26 + 'a')
    }
    mp[k] = append(mp[k], s)
  }
  var ans [][]string
  for _, v := range mp {
    ans = append(ans, v)
  }
  return ans
}