package jckeep.trie;

import java.util.*;


class TrieNode {
    public TrieNode[] children;
    public String word;

    public TrieNode() {
        children = new TrieNode[26];
    }
}


public class Trie {
    private TrieNode trie;

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

    public void insert(String word) {
        TrieNode node = trie;
        for (int i = 0; i < word.length(); ++i) {
            char c = word.charAt(i);
            if (node.children[c - 'a'] == null) {
                node.children[c - 'a'] = new TrieNode();
            }
            node = node.children[c - 'a'];
        }
        node.word = word;
    }

    public boolean search(String word) {
        if (word == null || word.length() == 0)
            return true;
        TrieNode node = trie;
        for (int i = 0; i < word.length(); ++i) {
            char c = word.charAt(i);
            if (node.children[c - 'a'] == null)
                return false;
            node = node.children[c - 'a'];
        }
        return (word.equals(node.word) ? true : false);
    }

    public boolean searchPrefix(String prefix) {
        if (prefix == null || prefix.length() == 0)
                        return true;
                TrieNode node = trie;
                for (int i = 0; i < prefix.length(); ++i) {
                        char c = prefix.charAt(i);
                        if (node.children[c - 'a'] == null)
                                return false;
                        node = node.children[c - 'a'];
                }
        return true;
    }
}