Java HashMap & Trie with explanation, beat 100%, 25ms


  • 3
    L

    For searching word problems, the first thing comes to my mind is always trie.
    In this problem, we actually check if this word has prefix with other words that has same length, start and end;
    The naive way is build the whole trie for all words, which require large space if there are many long words.
    So my approach is,

    1. Build a map, abbr->Trie, where abbr=s[0]+len+s[len-1]

    2. For a new word, if abbr is not in the map, create a new Trie for this abbr, but only push further to the 1st char, and then memorize the idx of the word at this trie node;

    3. For a new word, if abbr is in the map, continue search in the trie till the current char can not be matched. And here we have 2 situation:
      (1) the idx memorized under this trie node is -1, which means that the word that has same prefix with current word has longer prefix with other words, then we just create a new trie node for the current word and memorize the current idx;
      (2) the idx memorized under this trie node is not -1, which means that the word memorized here has same prefix with current word and currently they share the longest prefix in this abbr. Thus, we need to push further for both words until the 1st different char. And also, we need to set the idx memorized before to -1.

    Since we do not build the suffix of the word in the trie until there is another word has same prefix, the space complexity for the trie with abbr is O(n*longestSamePrefixLength).

    Code:

    class Solution {
    public List<String> wordsAbbreviation(List<String> dict) {
        abbr2trie = new HashMap<>();
        endIdx = new int[dict.size()];
        for(int i = 0; i<dict.size(); ++i){
            String cur = dict.get(i);
            if(cur.length()<=3) endIdx[i] = cur.length();
            else{
                addWord(cur, str2abbr(cur), i, dict);
            }
        }
        List<String> res = new LinkedList<>();
        for(int i = 0; i<dict.size(); ++i){
            String cur = dict.get(i);
            if(cur.length()-endIdx[i]-1<=1) res.add(cur);
            else{
                res.add(cur.substring(0, endIdx[i])+(cur.length()-endIdx[i]-1)+cur.charAt(cur.length()-1));
            }
        }
        return res;
    }
    private Map<String, TrieNode> abbr2trie;
    private int[] endIdx;
    class TrieNode{
        int stringIndex;
        TrieNode[] next;
        public TrieNode(){
            stringIndex = -1;
            next = new TrieNode[26];
        }
        public TrieNode(int i){
            stringIndex = i;
            next = new TrieNode[26];
        }
    }
    private String str2abbr(String s){
        return s.charAt(0)+String.valueOf(s.length())+s.charAt(s.length()-1);
    }
    private void addWord(String s, String abbr, int sidx, List<String> dict){
        if(!abbr2trie.containsKey(abbr)){
            // 1st word with this abbr
            // Only create 1st char of the string in the trie
            TrieNode head = new TrieNode();
            abbr2trie.put(abbr, head);
            head.next[s.charAt(0)-'a'] = new TrieNode(sidx);
            endIdx[sidx] = 1;
        }
        else{
            TrieNode node = abbr2trie.get(abbr);
            int idx = 0;
            while(node.next[s.charAt(idx)-'a']!=null){
                // Go through same preffix in the trie
                node = node.next[s.charAt(idx++)-'a'];
            }
            int sidx2 = node.stringIndex;
            if(sidx2==-1){
                // This means that other words with this prefix have been pushed further, they have longer same prefix
                // And this word could stop here and create next char to distinguish it
                node.next[s.charAt(idx)-'a'] = new TrieNode(sidx);
                endIdx[sidx] = idx+1;
                return;
            }
            // Push further sidx2
            node.stringIndex = -1;
            
            String s2 = dict.get(sidx2);
            while(s.charAt(idx)==s2.charAt(idx)){
                node.next[s.charAt(idx) - 'a'] = new TrieNode();
                node = node.next[s.charAt(idx++) -'a'];
            }
            endIdx[sidx]  = idx+1;
            endIdx[sidx2] = idx+1;
            node.next[s.charAt(idx)-'a'] = new TrieNode(sidx);
            node.next[s2.charAt(idx)-'a'] = new TrieNode(sidx2);
        }
    }
    }

  • 0
    R
    This post is deleted!

Log in to reply
 

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