820. Short Encoding of Words

二刷 06/2022

Version #1 Trie + DFS

和一刷写的基本一样

看到答案有一个优化就是记录每一个TrieNode的children count，然后用一个hashmap把所有的TrieNode存起来，最后iterate一遍所有的TrieNode，如果children count是0，就是leaf 这样可以避免再做一次dfs

Time O(Sum{word length})

Space O(Sum{word length})

Runtime: 33 ms, faster than 64.02% of Java online submissions for Short Encoding of Words.

Memory Usage: 59 MB, less than 47.56% of Java online submissions for Short Encoding of Words.

一刷class Solution {

    class TrieNode {

        TrieNode[] children;

        boolean isWord;

        public TrieNode() {

            children = new TrieNode[26];

        }

    }

    private void addWord(TrieNode root, String word) {

        for (int i = word.length() - 1; i >= 0; i--) {

            int index = word.charAt(i) - 'a';

            if (root.children[index] == null) {

                root.children[index] = new TrieNode();

            }

            root = root.children[index];

        }

        root.isWord = true;

    }

    public int minimumLengthEncoding(String[] words) {

        // Build a suffix trie with the revered order of all words

        // Search for all the leaf nodes and add up their depth + 1 '#'

        TrieNode root = new TrieNode();

        for (String word : words) {

            addWord(root, word);

        }

        int[] result = new int[1];

        dfs(root, 0, result);

        return result[0];

        // root

        //    t

        //     \ 

        //      isWord

    }

    

    private void dfs(TrieNode node, int depth, int[] result) {

        boolean isLeaf = true;

        for (int i = 0; i < 26; i++) {

            if (node.children[i] != null) {

                isLeaf = false;

                dfs(node.children[i], depth + 1, result);

            }

        }

        if (isLeaf) {

            result[0] += depth + 1;

        }

    }

}

Version #1 Trie + DFS

The complexity of creating a trie is O(W*L), where W is the number of words, and L is an average length of the word: you need to perform L lookups on the average for each of the W words in the set.

Same goes for looking up words later: you perform L steps for each of the W words.

/*
root
\
 e
  \
   m
*/

 81.33 %
class Solution {
    class Trie {
        Trie[] children;
    }
    public int minimumLengthEncoding(String[] words) {
        // build trie for reversed word
        // e.g. time -> e-m-i-t, me -> e-m  so time and me will share the same e-m path
        // we build the result with the longest length of each path
        Trie root = new Trie();
        for (String word : words) {
            add(root, word);
        }
        int[] result = new int[1];
        dfs(root, result, 1);
        return result[0];
    }
   
    private void dfs(Trie node, int[] result, int path) {
        if (node.children == null) { // isleaf
            result[0] += path;
            return;
        }
        for (int i = 0; i < 26; i++) {
            if (node.children[i] != null) {
                dfs(node.children[i], result, path + 1);
            }
        }
    }
   
    private void add(Trie root, String word) {
        Trie curr = root;
        for (int i = word.length() - 1; i >= 0; i--) {
            int index = word.charAt(i) - 'a';
            if (curr.children == null) {
                curr.children = new Trie[26];
            }
            if (curr.children[index] == null) {
                curr.children[index] = new Trie();
            }
            curr = curr.children[index];
        }
    }
}