Nuggets team number online, help you Offer impromptu! Click for details

Topic describes

A Trie (pronounced like “try”) or prefix tree is a tree data structure for efficiently storing and retrieving keys in a string data set. This data structure has a number of applications, such as auto-completion and spell checking.

Please implement Trie class:

Trie() initializes the prefix tree object. Void insert(String word) Inserts the String word into the prefix tree. Boolean search(String word) Returns true if the String word is in the prefix tree (that is, inserted before retrieval); Otherwise, return false. Boolean startsWith(String prefix) Returns true if one of the prefixes of the previously inserted String word is prefix; Otherwise, return false.

Example:

The input

[“Trie”, “insert”, “search”, “search”, “startsWith”, “insert”, “search”] [[], [“apple”], [“apple”], [“app”], [“app”], [“app”], [“app”]]

The output

[null, null, true, false, true, null, true]

explain

Trie trie = new Trie(); trie.insert("apple"); trie.search("apple"); // Return True trie.search("app"); // Return False trie.startswith ("app"); // Return True trie.insert("app"); trie.search("app"); / / return TrueCopy the code

Thought analysis

• This is a design topic, we need to take the initiative to design the data structure, there is a certain challenge.
• The dictionary tree is a classic data structure for string processing. The most common application is to find out if a string has been present before.
• The dictionary tree is also the basis of AC automata, we need to grasp seriously!

code

class Trie {
    private TrieNode root;

    /** Initialize your data structure here. */
    public Trie(a) {
        root = new TrieNode();
    }
    
    /** Inserts a word into the trie. */
    public void insert(String word) {
        TrieNode node = root;
        for (char ch : word.toCharArray()) {
            if(! node.containsKey(ch)) { node.put(ch,new TrieNode());
            }
            node = node.get(ch);
        }
        node.setEnd();
    }
    
    /** Returns if the word is in the trie. */
    public boolean search(String word) {
        TrieNode node = searchPrefix(word);
        returnnode ! =null && node.isEnd();
    }
    
    /** Returns if there is any word in the trie that starts with the given prefix. */
    public boolean startsWith(String prefix) {
        TrieNode node = searchPrefix(prefix);
        returnnode ! =null;
    }

    public TrieNode searchPrefix(String prefix) {
        TrieNode node = root;
        for (char c : prefix.toCharArray()) {
            if (node.containsKey(c)) {
                node = node.get(c);
            } else {
                return null; }}returnnode; }}class TrieNode {
    private TrieNode[] links;
    private final int R = 26;
    private boolean isEnd;
    
    public TrieNode (a) {
        links = new TrieNode[R];
    }

    public boolean containsKey(char ch) {
        return links[ch - 'a'] != null;
    }

    public TrieNode get(char ch) {
        return links[ch - 'a'];
    }

    public void put(char ch, TrieNode node) {
        links[ch - 'a'] = node;
    }

    public void setEnd(a) {
        isEnd = true;
    }

    public boolean isEnd(a) {
        returnisEnd; }}/** * Your Trie object will be instantiated and called as such: * Trie obj = new Trie(); * obj.insert(word); * boolean param_2 = obj.search(word); * boolean param_3 = obj.startsWith(prefix); * /
Copy the code

conclusion

• Common data design topics are not very difficult, the topic change is small, as long as we practice a few times, this knowledge point can master!
• Stick to the daily question, come on!