Shortest unique prefix to represent word in an array

看到prefix肯定想到的是trie咯，在trie node里面多加一个field count，表示
这个字符出现多少次
1，insert word into the trie
2, search the word, 找到第一个count为1的node，返回
因为说明这个node下面没有分支了，他就应该是唯一的

/*
 * 求一个string list的每个string对应的unique prefix，返回也是一个list
 */
public class TriePrefix {
	
	public static final int R = 256;
	private Node root;
	
	private class Node{
		private int count;
		private boolean isEnd;
		private Node next[] = new Node[R];
		
		public Node(){
			count = 0;
			isEnd = false;
		}

		public Node(int count, boolean isEnd){
			this.count = count;
			this.isEnd = isEnd;
		}
	}
	
	public void insert(String str){
		if(root == null) root = new Node();
		Node curr = root;
		for(int i = 0; i < str.length(); i++){
			char c = str.charAt(i);
			if(curr.next[c] == null){
				curr.next[c] = new Node(1, false);
			}else{
				curr.next[c].count++;
			}
			curr = curr.next[c];
		}
		curr.isEnd = true;
	}
	
	public String shortestPrefix(String str){
		Node curr = root;
		int len = 0;
		for(int i = 0; i < str.length(); i++){
			char c = str.charAt(i);
			curr = curr.next[c];
			len++;
			if(curr.count == 1) break;
		}
		return str.substring(0, len);
	}
	
	public static void main(String[] args){
		TriePrefix trie = new TriePrefix();
		String[] words = {"by", "sea", "sells", "she", "shells", "shore", "the"};
		String[] words1 = {"zebra", "dog", "duck", "dove"};
		for(String word : words1){
			trie.insert(word);
		}
		String[] res = new String[words1.length];
		for(int i = 0; i < words1.length; i++){
			res[i] = trie.shortestPrefix(words1[i]);
			System.out.println(res[i]);
		}
	}

}