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>> ans = new ArrayList<List<String>>();
        Map<String, List<String>> map = new HashMap<String, List<String>>();

        for(String s: strings) {
            String shifted = shift(s);
            if(!map.containsKey(shifted)) map.put(shifted, new ArrayList<String>());
            map.get(shifted).add(s);
        }

        for(String key: map.keySet()) {
            ans.add(map.get(key));
        }
        return ans;
    }

    public String shift(String s) {
        if(s.length() == 0) return "";
        StringBuilder sb = new StringBuilder();
        int offset = s.charAt(0) - 'a';
        for(int i = 0; i < s.length(); i++) {
            int c = s.charAt(i) - 'a';
            sb.append( (char)( (c + 26 - offset) % 26) );
        }
        return sb.toString();
    }
}