1.6 Group Shifted Strings

Description

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"] ]

Method

since for a group, we can use the start of this sequence to stand of this group, so if we meet a string, we only need to transfer it by changing the first character to start with 'a' or some chacter to get the key of each group;

Time and Space Complexity

t:o(n) s: o(n)

Code

public class Solution {

   public List<List<String>> groupStrings(String[] strings) {
       List<List<String>> ans = new ArrayList<List<String>>();
       if (strings == null || strings.length == 0){
           return ans;
       }
       HashMap<String, List<String>> map = new HashMap<>();
       for (String str : strings){
            if (str == null || str.length() == 0){
                continue;
            }
            int offset = 'z' - str.charAt(0);
            String key = "";
            for (char c : str.toCharArray()){
                 char a = (char) (((c - 'a') + offset) % 26 + 'a');
                 key += a;

            }
            if (map.containsKey(key)){
                map.get(key).add(str);
            } else {
                List<String> list = new ArrayList<String>();
                list.add(str);
                map.put(key, list);
            }
       }
       for (String key : map.keySet()){
            List<String> list = map.get(key);
            Collections.sort(list);
            ans.add(list);
       }
       return ans;
}

}