2021-02-17 208. 实现 Trie (前缀树)

题目地址

https://leetcode-cn.com/problems/implement-trie-prefix-tree/

题目描述

实现一个 Trie (前缀树)，包含 insert, search, 和 startsWith 这三个操作。

示例:
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

说明:
你可以假设所有的输入都是由小写字母 a-z 构成的。
保证所有输入均为非空字符串。

思路

1. 因为输入只有小写字母，所以每一层的分支最多只有26个。
2. 构建一个单词结束时标记结束位，说明有到这结束的单词。搜索时逐个字符往下找便可。
   如果不是字母，是其他的数字或者中文字符等等，只要做类似的映射也可这般搜索，比如用Map来存储往下的子树。

题解

/**
 * @Author: vividzcs
 * @Date: 2021/2/16 10:41 上午
 */
public class Trie {
    private TrieNode root;

    public static void main(String[] args) {
        Trie trie = new Trie();

        trie.insert("apple");
        boolean result = trie.search("apple");   // 返回 true
        System.out.println(result);
        result = trie.search("app");     // 返回 false
        System.out.println(result);
        result = trie.startsWith("app"); // 返回 true
        System.out.println(result);
        trie.insert("app");
        result = trie.search("app");     // 返回 true
        System.out.println(result);
    }

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

    /** Inserts a word into the trie. */
    public void insert(String word) {
        TrieNode currentNode = root;
        for (int i=0; i<word.length(); i++) {
            char currentChar = word.charAt(i);
            if (!currentNode.containsNode(currentChar)) {
                currentNode.put(currentChar, new TrieNode());
            }
            currentNode = currentNode.getNext(currentChar);
        }
        currentNode.setEnd();
    }

    /** Returns if the word is in the trie. */
    public boolean search(String word) {
        TrieNode node = matchPrefix(word);
        return node != null && node.isEnd();
    }

    private TrieNode matchPrefix(String word) {
        if (word == null || word.length() == 0) {
            return null;
        }
        TrieNode currentNode = root;
        for (int i=0; i<word.length(); i++) {
            char currentChar = word.charAt(i);
            if (!currentNode.containsNode(currentChar)) {
                return null;
            }
            currentNode = currentNode.getNext(currentChar);
        }
        return currentNode;
    }

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

/**
 * @Author: vividzcs
 * @Date: 2021/2/16 10:23 上午
 */
public class TrieNode {
    private TrieNode[] nexts;
    private final int LEVEL_MAX_SIZE = 26;
    private boolean end;

    public TrieNode() {
        this.nexts = new TrieNode[LEVEL_MAX_SIZE];
    }

    public boolean containsNode(char key) {
        return nexts[key - 'a'] != null;
    }

    public TrieNode getNext(char key) {
        return nexts[key - 'a'];
    }

    public void put(char key, TrieNode node) {
        if (!containsNode(key)) {
            nexts[key - 'a'] = node;
        }
    }

    public boolean isEnd() {
        return end;
    }

    public void setEnd() {
        this.end = true;
    }


    public TrieNode[] getNexts() {
        return nexts;
    }

    public void setNexts(TrieNode[] nexts) {
        this.nexts = nexts;
    }

    public int getLEVEL_MAX_SIZE() {
        return LEVEL_MAX_SIZE;
    }
}