Algorithm_Collection/leetcode_java/T208_implment_trie.java at master · dotastar/Algorithm_Collection

75 lines (63 loc) · 1.83 KB

class TrieNode {
    private final int R = 26;
    private final TrieNode[] children;
    private String item;

    public TrieNode() {
        children = new TrieNode[R];
        item = "";
    }

    public String getItem() {
        return item;
    }

    public void setItem(String item) {
        this.item = item;
    }

    public TrieNode[] getChildren() {
        return children;
    }

    public TrieNode getChild(int i) {
        if (i >= 26 || i < 0) throw new IllegalArgumentException();
        return children[i];
    }

    public void setChild(int i, TrieNode node) {
        children[i] = node;
    }
}

public class Trie {
    private TrieNode root;

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

    // Inserts a word into the trie.
    public void insert(String word) {
        TrieNode curr = root;
        for (char c : word.toCharArray()) {
            if (curr.getChild(c - 'a') == null) curr.setChild(c - 'a', new TrieNode());
            curr = curr.getChild(c - 'a');
        }
        curr.setItem(word);
    }

    // Returns if the word is in the trie.
    public boolean search(String word) {
        TrieNode curr = root;
        for (char c : word.toCharArray()) {
            if (curr.getChild(c - 'a') == null) return false;
            curr = curr.getChild(c - 'a');
        }
        return curr.getItem().equals(word);
    }

    // Returns if there is any word in the trie
    // that starts with the given prefix.
    public boolean startsWith(String prefix) {
        TrieNode curr = root;
        for (char c : prefix.toCharArray()) {
            if (curr.getChild(c - 'a') == null) return false;
            curr = curr.getChild(c - 'a');
        }
        return true;
    }
}

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

Provide feedback

Saved searches

Use saved searches to filter your results more quickly

Uh oh!

Expand file tree

Search code, repositories, users, issues, pull requests...

Uh oh!

FilesExpand file tree

T208_implment_trie.java

Latest commit

History

T208_implment_trie.java

File metadata and controls

Expand file tree