Java Verbose&Clear 24ms (99%) Trie-based solution


  • 1

    First the code:

    public class Solution {
        public static class Node {
            String word = null;
            Node[] ar = new Node[26];
        }
    
        public String replaceWords(List<String> dict, String sentence) {
            if (dict.size() == 0 || sentence.length() == 0)
                return "";
            StringBuilder sb = new StringBuilder();
            String[] words = sentence.split(" ");
            Node root = new Node();
            for (String s : dict) {
                insert(root, s.toCharArray(), 0);
            }
            for (int i = 0; i < words.length; i++) {
                sb.append(get(root, words[i].toCharArray(), 0));
                if (i < words.length - 1)
                    sb.append(" ");
            }
            return sb.toString();
        }
    
        public void insert(Node node, char[] chs, int index) {
            if (node.word != null)
                return;
            if (index == chs.length) {
                node.word = String.valueOf(chs);
                return;
            }
            char ch = chs[index];
            if (node.ar[ch - 'a'] == null) {
                node.ar[ch - 'a'] = new Node();
            }
            insert(node.ar[ch - 'a'], chs, index + 1);
        }
    
        public String get(Node node, char[] chs, int index) {
            if (node.word != null)
                return node.word;
            if (index >= chs.length)
                return String.valueOf(chs);
            char ch = chs[index];
            if (node.ar[ch - 'a'] == null)
                return String.valueOf(chs);
            return get(node.ar[ch - 'a'], chs, index + 1);
        }
    }
    

    This is a typical trie problem and the algorithm required to solve this one is also very typical. You only need to implement insert so that you can build a trie, and then get so that you can get the root for every successor.

    My approach of handling the trie is inspired by the approach taken by Robert Sedgwick in his book of Algorithms

    • Each node has 26 pointers downward. Also each node stands for a particular character on a particular index.
    • Each node can store a word. It is the accumulation of all the characters on the path from root to itself. It is only stored here, when we walk down from the root, and reaches the end of the key on this node. So a lot of nodes actually have their word attribute as null.

    This is not a hard trie problem, and the code is quite clear. One little trick: in get, when you found that the current node has a word, then you return since this is the shortest root found, this is trivially obvious; but in insert, you should actually do the same, because for example: if you have the key as ratt and is trying to insert it, and you arrived at a node whose word is rat, then you should just abort here: there is no need to store ratt in some node downward anyway, since it will never be retrieved during the get loop.

    The performance is 24ms (99%) @ 2017-08-04 20:10:47.

    The complexity IMO is O(size_of_dict) (in the unit of character, so it's like sum of all root_lengths) for building the trie, and O(number_of_words_in_sentence * length_of_longest_root_in_dict) for the lookup.


Log in to reply
 

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