Leetcode: 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.

Understand the problem:
The problem looks quite like the grouping anagrams. So the idea is the same: for each string, find out its "original" format, and check if the hash map contains this original string. If yes, put into the map. 

Code (Java):

public class Solution {
    public List<List<String>> groupStrings(String[] strings) {
        List<List<String>> result = new ArrayList<List<String>>();
        if (strings == null || strings.length == 0) {
            return result;
        }
        
        Arrays.sort(strings, new LexComparator());
        
        Map<String, List<String>> map = new HashMap<String, List<String>>();
        
        for (String s : strings) {
            StringBuffer sb = new StringBuffer();
            int distance = Character.getNumericValue(s.charAt(0)) - 'a';
            for (int i = 0; i < s.length(); i++) {
                int val = Character.getNumericValue(s.charAt(i)) - distance;
                val = val < 'a' ? val + 26 : val;
                char ori = (char) val;
                sb.append(ori);
            }
            String original = sb.toString();
            if (map.containsKey(original)) {
                List<String> list = map.get(original);
                list.add(s);
                map.put(original, list);
            } else {
                List<String> list = new ArrayList<String>();
                list.add(s);
                map.put(original, list);
            }
        }
        
        // Iterate the map
        Iterator it = map.entrySet().iterator();
        while (it.hasNext()) {
            Map.Entry pair = (Map.Entry) it.next();
            result.add((List<String>) pair.getValue());
        }
        
        return result;
    }
    
    private class LexComparator implements Comparator<String> {
        @Override
        public int compare(String a, String b) {
            if (a.length() != b.length()) {
                return a.length() - b.length();
            }
            
            for (int i = 0; i < a.length(); i++) {
                if (a.charAt(i) != b.charAt(i)) {
                    return a.charAt(i) - b.charAt(i);
                }
            }
            return 0;
        }
    }
}

Update on 12/5/18:

class Solution {
    public List<List<String>> groupStrings(String[] strings) {
        List<List<String>> ans = new ArrayList<>();
        if (strings == null || strings.length == 0) {
            return ans;
        }
        
        Map<String, List<String>> map = new HashMap<>();
        
        for (String str : strings) {
            String key = findKey(str);
            if (map.containsKey(key)) {
                map.get(key).add(str);
            } else {
                List<String> list = new ArrayList<>();
                list.add(str);
                map.put(key, list);
            }
        }
        
        // iterate the map
        //
        for (List<String> value : map.values()) {
            ans.add(value);
        }
        
        return ans;
    }
    
    private String findKey(String str) {
        StringBuilder sb = new StringBuilder();
        
        int distance = str.charAt(0) - 'a';
        
        for (int i = 0; i < str.length(); i++) {
            char c = str.charAt(i);
            char o = (char) (c - distance);
            if (o < 'a') {
                o = (char) (o + 26);
            }
            sb.append(o);
        }
        
        return sb.toString();
    }
}