208. Implement Trie (Prefix Tree) (Medium)

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

Implement a trie with insert, search, and startsWith methods.

Example:

Trie trie = new Trie();

trie.insert("apple");
trie.search("apple");   // returns true
trie.search("app");     // returns false
trie.startsWith("app"); // returns true
trie.insert("app");   
trie.search("app");     // returns true

Note:

  • You may assume that all inputs are consist of lowercase letters a-z.
  • All inputs are guaranteed to be non-empty strings.

Solutions

class Trie {
    // This problem is quite trivial and requires mass caution.

    String sequence = "";
    String word = null;

    Map<Character, Trie> subTries = new HashMap<>();

    /** Initialize your data structure here. */
    public Trie() {

    }

    // TODO when we process the ith char in the word, the ith char should not be included by current trie.

    // create trie node for ith node
    private void insert(String word, int i) {

        // current word ending at i represents current trie is not only a prefix trie, there
        // are also words affiliate to it.

        // FIXME below commented out statements are incorrect
        /*
            if (i == word.length() - 1) {
                this.word = word;
            }
        */

        if (i == word.length()) {
            this.word = word;

            // do not forget below one
            this.sequence = word.substring(0, i);

            return;
        }

        // substring(i) means trunk the string starting from i, not ending to i

        // I made a mistake word.substring(0, i + 1), actually, ith char should not be included
        // for current trie
        this.sequence = word.substring(0, i);

        char c = word.charAt(i);
        // create a sub trie if not exists
        if (!subTries.keySet().contains(c)) {
            subTries.put(c, new Trie());
        }

        subTries.get(c).insert(word, i + 1);
    }

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

    private boolean search(String word, int i) {
        // the exit
        if (i == word.length()) {
            // this.word != null indicates it's not only a prefix, but also representing a word.
            if (this.word != null && this.word.equals(word)) {
                return true;
            }

            return false;
        }


        char c = word.charAt(i);
        if (!subTries.keySet().contains(c)) {
            return false;
        }

        return subTries.get(c).search(word, i + 1);
    }

    /** Returns if the word is in the trie. */
    public boolean search(String word) {
        return search(word, 0);
    }

    private boolean startsWith(String prefix, int i) {
        // the exit
        if (i == prefix.length()) {
            if (this.sequence.equals(prefix)) {
                return true;
            }

            return false;
        }


        char c = prefix.charAt(i);
        if (!subTries.keySet().contains(c)) {
            return false;
        }

        return subTries.get(c).startsWith(prefix, i + 1);
    }

    /** Returns if there is any word in the trie that starts with the given sequence. */
    public boolean startsWith(String prefix) {
        return startsWith(prefix, 0);
    }
}

Incorrect Solutions

References

Copyright © iovi.com 2017 all right reserved,powered by GitbookLast Modification: 2019-12-03 11:01:17

results matching ""

    No results matching ""