LintCode 442 · Implement Trie (Prefix Tree).java

	// Approach #1 - Trie - Data Structure implementation.
	// T O(h) for all the 3 searching functions, given that h is the height of the tree.
	public class Trie {
	private TrieNode root;
	public Trie() {
	// do intialization if necessary
	root = new TrieNode();
	}
	/*
	* @param word: a word
	* @return: nothing
	*/
	public void insert(String word) {
	// write your code here
	TrieNode node = root;
	for (int i = 0; i < word.length(); i++) {
	char letter = word.charAt(i);
	if (!node.sons.containsKey(letter)) {
	node.sons.put(letter, new TrieNode());
	}
	node = node.sons.get(letter);
	}
	node.word = word;
	node.isWord = true;
	}
	/*
	* @param word: A string
	* @return: if the word is in the trie.
	*/
	public boolean search(String word) {
	// write your code here
	TrieNode node = root;
	for (int i = 0; i < word.length(); i++) {
	char letter = word.charAt(i);
	if (!node.sons.containsKey(letter)) {
	return false;
	}
	node = node.sons.get(letter);
	}
	return node.isWord;
	}
	/*
	* @param prefix: A string
	* @return: if there is any word in the trie that starts with the given prefix.
	*/
	public boolean startsWith(String prefix) {
	// write your code here
	TrieNode node = root;
	for (int i = 0; i < prefix.length(); i++) {
	char letter = prefix.charAt(i);
	if (!node.sons.containsKey(letter)) {
	return false;
	}
	node = node.sons.get(letter);
	}
	return true;
	}
	private class TrieNode {
	public String word;
	public boolean isWord;
	public Map<Character, TrieNode> sons;
	public TrieNode() {
	this.word = null;
	this.isWord = false;
	sons = new HashMap<>();
	}
	public TrieNode(String word, boolean isWord) {
	this.word = word;
	this.isWord = isWord;
	sons = new HashMap<>();
	}
	}
	}

view raw LintCode 442 · Implement Trie (Prefix Tree).java hosted with ❤ by GitHub