Group Shifted Strings

Source

• leetcode: 249

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.

java

public List<List<String>> groupStrings(String[] strings) {  
    List<List<String>> ret = new ArrayList<List<String>>();  
    if (strings == null) return ret;  
    HashMap<String, List<String>> map = new HashMap<String, List<String>>();  
    for (String s : strings) {  
        int offset = s.charAt(0) - 'a';  
        String key = "a";  
        for (int i = 1; i < s.length(); i++) {  
            char c = (char)(s.charAt(i) - offset);  
            if (c < 'a')  
                c += 26;  
            key += c;  
        }  
        if (!map.containsKey(key)) {  
            map.put(key, new ArrayList<String>());  
        }  
        map.get(key).add(s);  
    }  
    for (List<String> list : map.values()) {  
        Collections.sort(list);  
        ret.add(list);  
    }  
    return ret;  
}