4 ms Java with detailed explaination


  • 0
    N
    1. "a", "b", "c"..."z" will be grouped as a string with single letter
    2. "ab", "bc" will be grouped because 'b'-'a' == 'c'-'b'. So can have a method to find the shifting pattern. "ab" --> 'b' - 'a' = 1. Then make a string "b" that equally means the original string contains two characters with shifting 1.
        public List<List<String>> groupStrings(String[] strings) {
            List<List<String>> res = new ArrayList<List<String>>();
            
            if (strings == null || strings.length == 0) {
                return res;
            }
            
            HashMap<String, List<String>> map = new HashMap<String, List<String>>();    // group the strings with same shifting into a list
            
            for (int i = 0; i < strings.length; i++) {
                String s = getPattern(strings[i]);
                if (map.containsKey(s)) {
                    List<String> list = map.get(s);
                    list.add(strings[i]);
                    map.put(s, new ArrayList<String>(list));
                }
                else {
                    List<String> list = new ArrayList<String>();
                    list.add(strings[i]);
                    map.put(s, new ArrayList<String>(list));
                }
            }
            
            for (String s : map.keySet()) {
                res.add(map.get(s));
            }
            
            return res;
        }
        
        /* creates the pattern for string
        * "a" or "z" --> ""
        * "ab" --> 'a' + ('b' - 'a') --> "b"
        * "xy" --> 'a' + ('y' - 'x') --> "b"
        * The strings with same shifting scores can be grouped
        * @param String s
        * @return String
        **/
        private String getPattern(String s) {
            if (s.length() == 1) {
                return "";
            }
            
            char[] chars = s.toCharArray();
            char[] newChars = new char[chars.length - 1];
            
            for (int i = 0; i < newChars.length; i++) {
                newChars[i] = (char)('a' + (chars[i + 1] - chars[i] + 26) % 26);
            }
            return String.valueOf(newChars);
        }
    }

Log in to reply
 

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