Simple solution in JAVA with detailed explaination


  • 3
    S
    HashMap<List<Integer>, List<String>> map:
    

    for "abc","bcd","xyz", the key would be
    [3, 1, 1]
    [how many numbers, 2nd - 1st, 3rd - 2nd]

    for "az","ba", the key would be
    [2, 25]
    [how many numbers, 2nd - 1st]
    (NOTICE: for "ba": a - b, since a < b, the result would be 26 + 'a' - 'b')

    thus, we have one unique key as List<Integer> for each Group, the List<String> for each key would be each group's result

    finally, iterate through the res and sort each List<String>

    public class Solution {
        public List<List<String>> groupStrings(String[] strings) {
            List<List<String>> res = new ArrayList<List<String>>();
            HashMap<List<Integer>, List<String>> map = new HashMap<List<Integer>, List<String>>();
            for(int i=0; i<strings.length; i++) {
                List<Integer> curKey = new ArrayList<Integer>();
                String str = strings[i];
                int length = str.length();
                curKey.add(length);
                for(int j=1; j<length; j++) {
                    int offset = str.charAt(j) - str.charAt(j-1);
                    int val = offset > 0 ? offset : 26 + offset;
                    curKey.add(val);
                }
                if (map.containsKey(curKey)) {
                    List<String> tmp = map.get(curKey);
                    tmp.add(str);
                } else {
                    List<String> tmp = new ArrayList<String>();
                    tmp.add(str);
                    res.add(tmp);
                    map.put(curKey, tmp);
                }
            }
            for(int i=0; i<res.size(); i++) {
                List<String> tmp = res.get(i);
                Collections.sort(tmp);
            }
            return res;
        }
    }

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.