My two ways: Trie and HashMap


  • 0
    //Trie Tree  4ms
    public class Solution {
        class TrieNode{
            List<String> list;
            TrieNode[] interval = new TrieNode[26];
        }
        
        public List<List<String>> groupStrings(String[] strings) {
            List<List<String>> res = new ArrayList<List<String>>();
            if(strings == null){
                return res;
            }
            constructTree(strings, res);
            return res;
        }
        
        public void constructTree(String[] strings, List<List<String>> res){
            TrieNode root = new TrieNode();
            for(String str : strings){
                TrieNode tempRoot = root;
                for(int i = 0; i < str.length() - 1; i++){
                    int inte = (str.charAt(i + 1) - str.charAt(i) + 26) % 26;
                    if(tempRoot.interval[inte] == null){
                        tempRoot.interval[inte] = new TrieNode();
                    }
                    tempRoot = tempRoot.interval[inte];
                }
                if(tempRoot.list == null){
                    tempRoot.list = new ArrayList<String>();
                    res.add(tempRoot.list);
                }
                tempRoot.list.add(str);
            }
        }
    }
    
    //HashMap  9ms
    public class Solution {
        public List<List<String>> groupStrings(String[] strings) {
            List<List<String>> res = new ArrayList<List<String>>();
            if(strings == null){
                return res;
            }
            Map<String, List<String>> map = new HashMap<String, List<String>>();
            for(String str : strings){
                String temp = "";
                for(int i = 0; i < str.length() - 1; i++){
                    temp += (str.charAt(i + 1) - str.charAt(i) + 26) % 26;
                }
                if(map.containsKey(temp)){
                    List<String> value = map.get(temp);
                    value.add(str);
                    map.put(temp, value);
                }
                else{
                    List<String> value = new ArrayList<String>();
                    value.add(str);
                    map.put(temp, value);
                }
            }
            for(List<String> list : map.values()){
                res.add(list);
            }
            return res;
        }
    }
    

Log in to reply
 

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