数据结构—— Trie (前缀树)

实现一个 Trie (前缀树)，包含插入, 查询, 和查询前缀这三个操作。
Trie trie = new Trie();
trie.insert(“apple”);
trie.search(“apple”); // 返回 true
trie.search(“app”); // 返回 false
trie.startsWith(“app”); // 返回 true
trie.insert(“app”);
trie.search(“app”); // 返回 true

思路:构造一个多叉树数据结构,每个父节点最多有26个子节点,分别表示26个字母,同时每个节点还存在一个结尾标志位,表示该节点是否位一个单词的末尾节点。树的操作是重点,首先在全局变量中,我们得到树的根节点,每次操作都从根节点出发。
插入操作就是遍历树,如果不存在相应的节点则实例化新节点,直到遍历到尾节点,并将尾节点的标志置为。
查询和查询前缀的方法类似,对树进行遍历,不存在节点直接返回false,最后返回判断尾节点的标志位。

class Node {

    public Node[] val;

    public boolean isEnd = false;

    public Node() {

        val = new Node[26];

    }

}

class Trie {

    Node root;

    /** Initialize your data structure here. */

    public Trie() {

        root = new Node();

    }

    /** Inserts a word into the trie. */

    public void insert(String word) {

        Node cur = root;

        for(int i = 0; i < word.length(); i ++) {

            if(cur.val[word.charAt(i) - 'a'] == null) {

                cur.val[word.charAt(i) - 'a'] = new Node();

            }

            cur = cur.val[word.charAt(i) - 'a'];

        }

        cur.isEnd = true;

    }

    /** Returns if the word is in the trie. */

    public boolean search(String word) {

        Node cur = root;

        for(int i = 0; i < word.length(); i++) {

            if(cur.val[word.charAt(i) - 'a'] == null) return false;

            cur = cur.val[word.charAt(i) - 'a'];

        }

        return cur.isEnd;

    }

    /** Returns if there is any word in the trie that starts with the given prefix. */

    public boolean startsWith(String prefix) {

        Node cur = root;

        for(int i = 0; i < prefix.length(); i++) {

            if(cur.val[prefix.charAt(i) - 'a'] == null) return false;

            cur = cur.val[prefix.charAt(i) - 'a'];

        }

        return true;

    }

}

巴特西

数据结构—— Trie (前缀树)

最新文章

热门文章