• Trie
    • 1.1 什么是Trie树
    • Tire 和 HashMap的比较
  • Implement Trie
  • Add and Search Word - Data structure design
    • HashMap trie:
    • Array trie:
  • Word Search II (Snapchat)

Trie

11-22 Bobst

1.1 什么是Trie树

Trie树，即字典树，又称单词查找树或键树，是一种树形结构，是一种哈希树的变种。典型应用是用于统计和排序大量的字符串（但不仅限于字符串），所以经常被搜索引擎系统用于 文本词频统计。

它的优点是：最大限度地减少无谓的字符串比较，查询效率比哈希表高。 Trie的核心思想是空间换时间。利用字符串的公共前缀来降低查询时间的开销以达到提高效率的目的。

它有3个基本性质： 根节点不包含字符，除根节点外每一个节点都只包含一个字符。 从根节点到某一节点，路径上经过的字符连接起来，为该节点对应的字符串。 每个节点的所有子节点包含的字符都不相同。

这样一来我们查询和插入可以一起完成（重点体会这个查询和插入是如何一起完成的，稍后，下文具体解释），所用时间仅仅为单词长度，在这一个样例，便是10。

源自于retrieve

  1. 每个点都是26叉树，可以用hashmap来实现
  2. 有一个虚根节点root
  3. 单词结尾有一个isLeaf标记

主要操作是find, insert

Tire 和 HashMap的比较

空间：Trie优于HashMap，省去了相同前缀的空间

什么时候用？

查前缀的时候 一个个的字母 省空间

节点的定义

class TrieNode {
    char c;
    HashMap<Character, TrieNode> map = new HashMap<>();
    boolean hasWord;

    public TrieNode(){}
    public TrieNode(char c){
        this.c = c;
    }
}

Implement Trie

class TrieNode {
    // Initialize your data structure here.
    char c;
    HashMap<Character, TrieNode> children = new HashMap<>();
    boolean hasWord;

    public TrieNode() {

    }
    public TrieNode(char c) {
        this.c = c;
    }
}

public class Trie {
    private TrieNode root;

    public Trie() {
        root = new TrieNode();
    }

    // Inserts a word into the trie.
    public void insert(String word) {
        TrieNode cur = root;
        for(int i = 0; i < word.length(); i++) {
            char ch = word.charAt(i);
            if(!cur.children.containsKey(ch)) {
                cur.children.put(ch, new TrieNode(ch));
            } 
            cur = cur.children.get(ch);
            // 易错点
            if(i == word.length() - 1) {
                cur.hasWord = true;
            }

        }

    }

    // Returns if the word is in the trie.
    public boolean search(String word) {
        if(searchNode(word) == null) {
            return false;
        } else if(searchNode(word).hasWord) {
            return true;
        } else {
            return false;
        }

    }

    // Returns if there is any word in the trie
    // that starts with the given prefix.
    public boolean startsWith(String prefix) {
         if(searchNode(prefix) == null) {
            return false;
        } else {
            return true;
        }
    }

    public TrieNode searchNode(String word) {
        HashMap<Character, TrieNode> curChildren = root.children;
        TrieNode result = null;
        for(char c : word.toCharArray()) {
            if(curChildren.containsKey(c)) {
                // 易错点，先把 result给记录下来
                result = curChildren.get(c);
                curChildren = curChildren.get(c).children;
            } else {
                return null;
            }
        }
        return result;
    }
}

// Your Trie object will be instantiated and called as such:
// Trie trie = new Trie();
// trie.insert("somestring");
// trie.search("key");

Add and Search Word - Data structure design

上面这一题的加强版，多了一个wildcard匹配，当遇到'.'的时候，需要对当前节点的所有children进行遍历，需要多次尝试找到正确的起点，所以需要backtracking来做。

还有这一题为了可以应对大数据集的时候不会 超时，我们需要两点优化：

  1. 将hashmap改为array，array的访问比hashmap 还是要快很多
  2. 不要用substring的方法来进行递归，substring在java 7里面是O(n) 的时间复杂度，我们用pos 来定位当前char的位置

HashMap trie:

  • 优点 支持所有 Character 相对更省空间

  • 缺点 查询时间相对长 尤其是有 wildcard 做 DFS 时

Array trie:

  • 优点 查询速度快，尤其是有 wildcard 做 DFS 时

  • 缺点 每个 node 空间占用大 比较依赖指定字符集，比如 'a-z' 这种

体会一下用array如何来写的。

public class WordDictionary {

    class Node {
        char c;
        Node[] children;
        boolean isLeaf;
        Node() {
            children = new Node[26];
        }
        Node(char c) {
            this.c = c;
            children = new Node[26];
        }
    }

    Node root;
    public WordDictionary() {
        root = new Node();
    }

    // Adds a word into the data structure.
    public void addWord(String word) {
        Node t = root;
        for(int i = 0; i < word.length(); i++) {
            int id = word.charAt(i) - 'a';
            if(t.children[id] == null) {
                t.children[id] = new Node(word.charAt(i));
            }
            t = t.children[id];
        }

        t.isLeaf = true;
    }

    // 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, 0, root);
    }

    // dfs
    private boolean find(String word, int pos, Node node) {
        if(node == null) return false;
        if(word.length() == pos) return node.isLeaf;

        Node cur = node;

        if(word.charAt(pos) == '.') {
            for(Node key : cur.children) {
                // backtracking
                if( find(word, pos + 1,key) ) return true;
            }
            return false;
        } else if (cur.children[word.charAt(pos) - 'a'] != null) {
            return find(word, pos + 1,cur.children[word.charAt(pos) -'a']);
        } else {
            return false;
        }
    } 
}

Word Search II (Snapchat)

这一题其实是trie加 dfs+backtracking，如何边递归的同时边查询trie.

通过trie，可以做到递归每个字母的时候同时去检查这个字母是否是字典中某个单词的前缀，达到剪枝的目的。

backtracking就是记录当前的状态，去dfs的试下一个可能的状态，不成功的话回到当前记录的状态尝试另外一种可能。

因为是先添加新 char 然后直接 dfs 下个位置，并且在递归一开始添加单词，正确的检查位置是在边界检查之前，否则 ["a"] 和 ["a"] 的情况无法正确添加结果，因为 "a" 的四个方向都越界了

public class Solution {
    class TrieNode {
        char c;
        TrieNode[] children;
        boolean isLeaf;
        public TrieNode() {
            children = new TrieNode[26];
        }
        public TrieNode(char c) {
            this.c = c;
            children = new TrieNode[26];
        }
    }

    public List<String> findWords(char[][] board, String[] words) {
        List<String> result = new ArrayList<>();
        if(board == null || board.length == 0 || 
            board[0].length == 0 || words == null || words.length == 0) {
            return result;
        }

        // imaginary root
        TrieNode root = new TrieNode();

        for(String word : words) {
            insert(word, root);
        }

        for(int i = 0; i < board.length; i++) {
            for(int j = 0; j < board[0].length; j++) {
                dfs(board, i, j, root, new StringBuilder(), result);
            }
        }

        return result;
    }

    public void insert(String word, TrieNode root) {
        TrieNode cur = root;
        for(char c : word.toCharArray()) {
            int id = c - 'a';
            if(cur.children[id] == null) {
                cur.children[id] = new TrieNode(c);
            }
            cur = cur.children[id];
        }
        cur.isLeaf = true;
    }

    public void dfs(char[][] board, int i, int j, TrieNode node, StringBuilder sb, List<String> result) {
        // 想想为什么放在边界检查之前？
        // 当前的node isLeaf检查是晚于sb.append一步，此时边界已经越界了
        if(node.isLeaf) {
            if(!result.contains(sb.toString())) {
                result.add(sb.toString());
            }
        } 
        if(i < 0 || j < 0 || i >= board.length || j >= board[0].length) return;
        // 表示已经访问过了，避免死循环
        if(board[i][j] == '#') return;

        char c = board[i][j];
        int id = c - 'a';
        if(node.children[id] == null) {
            return;
        } else {
            int[] dx = {1, 0, -1, 0};
            int[] dy = {0, 1, 0, -1};

            int length = sb.length();
            for(int k = 0; k < 4; k++) {
                sb.append(c);
                board[i][j] = '#';
                dfs(board, i + dx[k], j + dy[k], node.children[id], sb, result);
                board[i][j] = c;
                // backtracking
                sb.setLength(length);
            }
        }
    }
}

results matching ""

    No results matching ""