Java O(nk) encoding method faster than sorting each string


  • 1

    I found the sol with top votes are the 2nd sol listed here. It basically sort each string in alphabetical order to get the key in hashtable, which is slow in big o notation, O(n klogk).
    This encoding method is faster as it never does the sorting. It just traverse through each char linearly and uses the frequency table to get a unique code for anagram. O(nk) n= strs.length, k=average length of str. In practice this might also faster. Image the case each string have 10000 chars. The encoded key is short. and k is faster than klogk

    public class Solution {
        public List<List<String>> groupAnagrams(String[] strs) {
            if (strs == null) {
                return new ArrayList<>();
            }
            Map<String, List<String>> map = new HashMap<>();
            for (String str : strs) {
                String key = encode(str);
                map.putIfAbsent(key, new ArrayList<>());
                map.get(key).add(str);
            }
            return new ArrayList<>(map.values());
        }
        // dacad: a2c1d2
        String encode(String word) {
            int[] frequency = new int[26];
            for (char c : word.toCharArray()) {
                frequency[c - 'a']++;
            }
            StringBuilder code = new StringBuilder();
            for (int i = 0; i < frequency.length; i++) {
                if (frequency[i] > 0) {
                    code.append('a' + i).append(frequency[i]);
                }
            }
            return code.toString();
        }
    }
    

    O(n klogk) n= strs.length, k=average length of str.

    public class Solution {
        public List<List<String>> groupAnagrams(String[] strs) {
            if (strs == null) {
                return new ArrayList<>();
            }
            Map<String, List<String>> map = new HashMap<>();
            for (String str : strs) {
                char[] chs = str.toCharArray();
                Arrays.sort(chs);
                String key = new String(chs);
                map.putIfAbsent(key, new ArrayList<>());
                map.get(key).add(str);
            }
            return new ArrayList<>(map.values());
        }
    }
    

  • 0
    R

    it is a great idea!


Log in to reply
 

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