Trie

• • level 1: 2 basic operations e.g. implement trie

  • level 2: customized search operation e.g. Replace Words

  • level 3: modified Trie Structure eg. palindrome pairs

Trie的核心思想是空间换时间，利用字符串的公共前缀来减少无谓的字符串比较，以达到提高查询效率的目的。

• Trie Tree和Tree的主要区别是节点的数据结构，Trie Tree的每个节点都包含两个属性，一个是字典或数组，用来存储当前节点的全部子节点，另一个是boolean，标记当前节点是否是叶节点。

• insert/search 效率高，时间复杂度O(L)，L是插入/查询的字符串的长度。

因为Trie树中不同的关键字不会产生冲突，而哈希搜索的效率通常取决于hash函数的好坏，若一个坏的hash函数导致很多的冲突，效率并不一定比Trie树高。

• 空间花费大。当hash函数很好时，Trie树的查找效率会低于哈希搜索。

implement Trie (Prefix tree)

basic operations: Trie template

注意search(String word) 和 startsWith(String prefix)的区别：

• search(String word) 需要check两个条件：TrieNode node == null , node.word == null

• startsWith(String prefix) 需要check一个条件: TrieNode node == null

class Trie {
    private class TrieNode{
        private TrieNode[] children;
        private String word;

        public TrieNode() {
            children = new TrieNode[26];
        }

        public void insert(String word, int index) {
            if (index == word.length()) {
                this.word = word;
                return;
            }
            int pos = word.charAt(index) - 'a';
            if (children[pos] == null) {
                children[pos] = new TrieNode();
            }
            children[pos].insert(word, index + 1);
        }

        public TrieNode find(String word, int index) {
            if (index == word.length()) {
                return this;
            }
            int pos = word.charAt(index) - 'a';
            if (children[pos] == null) {
                return null;
            }
            return children[pos].find(word, index + 1);
        }
    }

    private TrieNode root;
    /** Initialize your data structure here. */
    public Trie() {
        root = new TrieNode();
    }

    /** Inserts a word into the trie. */
    public void insert(String word) {
        root.insert(word, 0);
    }

    /** Returns if the word is in the trie. */
    public boolean search(String word) {
        TrieNode node = root.find(word, 0);
        return node == null ? false : node.word != null;    // check TrieNode is null or not, check node.word is null or not
    } 

    /** Returns if there is any word in the trie that starts with the given prefix. */
    public boolean startsWith(String prefix) {
        TrieNode node = root.find(prefix, 0);
        return node != null;
    }
}

note: also, we need to master iterative method for inserting word and find prefix word. 当你需要改写findWord()的时候，用iterative 更方便：

private boolean addWord(TrieNode root, String word) {

    TrieNode curr = root;
    for (char c : word.toCharArray()) {
        if (curr.next[c - 'a'] == null) {
            curr.next[c - 'a'] = new TrieNode();
        }
        curr = curr.next[c - 'a'];
    }
    curr.word = word;
    return true;
}

private String findWord(String s, TrieNode root) {

    if (root == null) return null;

    TrieNode node = root;
    for (char c : s.toCharArray()) {
        TrieNode cur = node.children[c - 'a'];
        if (cur == null) {
            return null;
        }

        if (cur.word != null) {
            return cur.word;
        }
        node = cur;
    }
    return null;
}

Add and Search Word - Data structure design

class WordDictionary {

    private class TrieNode{
        public TrieNode[] children;
        public String word;

        public TrieNode() {
            children = new TrieNode[26];
        }

        private void insert(String s, int index) {
            if (index == s.length()) {
                this.word = s;
                return;
            }

            int pos = s.charAt(index) - 'a';
            if (children[pos] == null) {
                children[pos] = new TrieNode();
            }
            children[pos].insert(s, index + 1);
        }
    }

    public TrieNode root;

    /** Initialize your data structure here. */
    public WordDictionary() {
        root = new TrieNode();
    }

    /** Adds a word into the data structure. */
    public void addWord(String word) {
        root.insert(word, 0);
    }

    /** Returns if the word is in the data structure. A word could contain the dot character '.' to represent any one letter. */
    public boolean search(String word) {
        return find(word, root, 0);
    }

    private boolean find(String word, TrieNode root, int index) {
        if (index == word.length()) return root.word != null;

        char c = word.charAt(index);
        if (c == '.') {
            for (int i = 0; i < 26; i++) {
                TrieNode node = root.children[i];
                if (node != null && find(word, node, index + 1)) {
                    return true;
                }
            }
            return false;
        } else {
            int pos = c - 'a';
            TrieNode node = root.children[pos];
            if (node == null) {
                return false;
            }
            return find(word, node, index + 1);
        }
    }
}

word search II

Given words =["oath","pea","eat","rain"]and char[][] board ,

这题BF做法是，对字典里的每个单词，用dfs检查它是否在matrix里面。如果只有一个或少量单词，和Word Search I一样。但如果字典有很多单词，复杂度很大。

使用Trie Tree。思路是把字典中所有单词加入trie tree，再对matrix每个位置的字符dfs，如果当前形成的单词不在trie里，就没必要继续搜下去，如果当前的单词在trie里，就说明可以在matrix里形成这个单词。类似number of island，check before visit。

naive brute force:

• runtime: O(m * n * O(4 ^ L) * k) where L is the average length of word, and k is # of words in words array, the real time complexity would be reduced due to some pruning operation.

• space: O(m * n)

trie tree:

• runtime: O(k * L + m * n * (4 ^ L))
• space: O(k * L + m * n)

class Solution {

    class TrieNode{
        TrieNode[] children;
        String word;

        public TrieNode() {
            children = new TrieNode[26];
        }

        public void insert(String word, int index) {
            if (index == word.length()) {
                this.word = word;
                return;
            }

            int pos = word.charAt(index) - 'a';
            if (children[pos] == null) {
                children[pos] = new TrieNode();
            }
            children[pos].insert(word, index + 1);
        }

        public TrieNode search(String word, int index) {
            if (index == word.length()) {
                return this;
            }
            int pos = word.charAt(index) - 'a';
            if (children[pos] == null) {
                return null;
            }
            return children[pos].search(word, index + 1);
        }
    }
    public List<String> findWords(char[][] board, String[] words) {
        List<String> res = new ArrayList<>();
        if (board == null || board.length == 0 || board[0].length == 0) return res;

        // build the trie tree
        TrieNode root = new TrieNode();
        for (String word : words) {
            root.insert(word, 0);
        }

        // dfs search
        int m = board.length;
        int n = board[0].length;
        boolean[][] visited = new boolean[m][n];
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                dfs(board, i, j, root, res, visited);
            }
        }
        return res;
    }

    private void dfs(char[][] board, int row, int col, TrieNode p, List<String> list, boolean[][] visited) {
        if (row < 0 || row >= board.length || col < 0 || col >= board[0].length || visited[row][col]) return;

        char c = board[row][col];
        if (p.children[c - 'a'] == null) {
            return;
        }

        p = p.children[c - 'a'];
        if (p.word != null) {
            list.add(p.word);
            p.word = null;
        }

        visited[row][col] = true;

        for (int[] pair : pairs) {
            int x = pair[0] + row;
            int y = pair[1] + col;

            dfs(board, x, y, p, list, visited);
        }

        visited[row][col] = false;
    }

    private final int[][] pairs = {{-1, 0}, {1, 0}, {0, 1}, {0, -1}};
}