Algorithm: Implement Trie Tree

Trie Tree

Trie Tree is called prefix tree or digital tree. It’s a type of k-ary search tree, a tree data structure used for locating specific keys rom within a set. These keys are most often strings, with links between nodes defined by characters.

For example, I have a bunch of strings.

What if I want to query if any string is existing in these strings?

I can check each string to get answer.

but what if I want to know, how many strings have similar prefix? how many strings prefix with “abc”? this is harder.

All of these problems can be solve efficiently by Trie Tree!

Implement a Trie Tree

public class MyTrie {
    public int containsTime(String str) {
		char[] carr = str.toCharArray();
		TrieNode cur = root;
		for (char c : carr) {
			if (cur.nexts[c - 'a'] == null) {
				return 0;
			}
			cur = cur.nexts[c - 'a'];
		}
		return cur.end;
	}

	public int containsPrefix(String prefix) {
		char[] carr = prefix.toCharArray();
		TrieNode cur = root;

		for (char c : carr) {
			if (cur.nexts[c - 'a'] == null) {
				return 0;
			}
			cur = cur.nexts[c - 'a'];
		}

		return cur.pass;
	}

	private void buildTrie(String[] strs) {
		root = new TrieNode('*');
		TrieNode cur;
		char[] carr;
		char c;

		for (String str : strs) {
			carr = str.toCharArray();
			cur = root;
			cur.pass++;
			for (int i = 0; i < carr.length; i++) {
				c = carr[i];
				if (cur.nexts[c - 'a'] == null) {
					cur.nexts[c - 'a'] = new TrieNode(c);
				}
				cur = cur.nexts[c - 'a'];
				cur.pass++;
				if (i == carr.length - 1) {
					cur.end++;
				}
			}

		}
	}

	class TrieNode {
		char value;
		TrieNode[] nexts;
		int pass = 0;
		int end = 0;

		public TrieNode(char v) {
			value = v;
			nexts = new TrieNode[24];
		}
	}
}