Sunday, October 30, 2016

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"],
Return:
[
  ["abc","bcd","xyz"],
  ["az","ba"],
  ["acef"],
  ["a","z"]
]
Note: For the return value, each inner list's elements must follow the lexicographic order.

Fairly easy, the difference between all successive letters and the first letter should be the same for string in the same group. Note that subsequent letters may be smaller than the first one, thus the difference can be calculated by ((currChar - firstChar) + 26) % 26.


public List<List<String>> groupStrings(String[] strings) {
        List<List<String>> rst = new ArrayList<>();
        if (strings.length == 0) {
            return rst;
        }
        Map<String, List<String>> map = new HashMap<>();
        for (String s : strings) {
            String key = "";
            if (s.length() == 1) {
                key = "1";
            } else {
                char first = s.charAt(0);
                for (int i = 1; i < s.length(); i++) {
                    key += ((s.charAt(i) - first) + 26) % 26;
                }
            }
            if (!map.containsKey(key)) {
                map.put(key, new ArrayList<>());
            }
            map.get(key).add(s);
        }

        for (List list : map.values()) {
            rst.add(list);
        }
        return rst;
    }


No comments:

Post a Comment