249. Group Shifted Strings

Question

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.

Algorithm

A similar question to the group anagram. Here we have to come up a standard way to shift all the strings to ensure after the shift, all the strings are guaranteed to have a fixed and certain output.

By saying this, I'm looking for a pivot. So I make the first character of each string as the pivot and shit it to 'a', then all the other characters shifted same offset accordingly.

Finally we use a map to group them. Key is the shifted string and value is the list of string than can shifted to the key.

Code

class Solution {
    public List<List<String>> groupStrings(String[] strings) {
        Map<String, List<String>> map = new HashMap<>();
        for (String str : strings) {
            String key = shift(str);
            map.putIfAbsent(key, new ArrayList<>());
            map.get(key).add(str);
        }
        List<List<String>> res = new ArrayList<>();
        res.addAll(map.values());
        return res;
    }
    
    private String shift(String str) {
        if (str == null || str.length() == 0) {
            return str;
        }
        int offset = str.charAt(0) - 'a';
        StringBuilder sb = new StringBuilder();
        for (Character ch : str.toCharArray()) {
            int shifted = ch - offset;
            if (shifted < 'a') {
                shifted += 26;
            }
            sb.append(shifted);
        }
        return sb.toString();
        
    }
}