249. Group Shifted Strings

Group Shifted Strings

Given a string, we can "shift" each of its letter to its successive letter, for example: "abc" -> "bcd". We can keep "shifting" which forms the sequence: "abc" -> "bcd" -> ... -> "xyz"

Given a list of strings which contains only lowercase alphabets, group all strings that belong to the same shifting sequence.

For example, given: ["abc", "bcd", "acef", "xyz", "az", "ba", "a", "z"], A solution is:

[ ["abc","bcd","xyz"], ["az","ba"], ["acef"], ["a","z"] ]

Solution

public class Solution {
    public List<List<String>> groupStrings(String[] strings) {
        List<List<String>> result = new ArrayList<>();
        if (strings == null || strings.length == 0) return result;

        Map<String, List<String>> map = new HashMap<>();
        for (String s : strings) {
            StringBuffer pattern = new StringBuffer();

            pattern.append("*");
            for (int i = 1; i < s.length(); i++) {
                int diff = s.charAt(i) - s.charAt(i - 1);
                while (diff <0) {
                    diff += 26;
                }

                pattern.append(diff);
                pattern.append("*");
            }

            List<String> current = new ArrayList<>();
            current.add(s);
            map.merge(pattern.toString(), current, (a, b) -> {
                a.addAll(b);
                return a;
            });
        }

        for (List<String> val : map.values()) {
            result.add(val);
        }

        return result;
    }
}