IBMは全世界で35万人の従業員がいます.名前は26文字で構成されています.長さは違います.1)アルゴリズムを設計してください.検索する名前を素早く見つけることができます.2)このアルゴリズムを書き出す時間の複雑さ3)このアルゴリズムをテストするなら、テストケースを書いてください.

面接問題:
IBMは全世界で35万人の従業員がいます.名前は26文字で構成されています.長さは違います.
1)アルゴリズムを設計してください.検索する名前を素早く見つけることができます.
2)このアルゴリズムを書く時間の複雑さ
3)このアルゴリズムをテストするなら、テストケースを書いてください.
 
方法:辞書ツリーのクイック検索を実現します.
 
辞書ツリー:ツリー構造であり、ハッシュツリーの変種である.典型的なアプリケーションは、統計、並べ替え、大量の文字列を保存するために使用されます.文字列に限らず、検索エンジンシステムによってしばしばテキストの語彙統計に使用されます.その利点は、文字列の共通プレフィックスを利用してクエリ時間を低減し、無駄な文字列比較を最大限に低減し、ハッシュツリーよりもクエリ効率が高いことである.

class Client_port {
	public static void main(String[] args) {
		Client_port cp = new Client_port();
		cp.insert("liuxin");
		System.out.println(cp.search_str("aaa"));
		System.out.println(cp.search_str("liuxin"));

	}

	private final int SIZE = 26; //             ，   SIZE         
	private Node root; //        

	private class Node {
		private boolean isStr; //                  
		private int num; //             。             
		private Node[] child; //        

		public Node() {
			child = new Node[SIZE];
			isStr = false;
			num = 1;
		}
	}

	public Client_port() {
		root = new Node();
	}

	/**
	 *                word
	 */
	public boolean search_str(String word) {
		Node pNode = this.root;
		for (int i = 0; i < word.length(); i++) {
			int index = word.charAt(i) - 'a';
			//             ，                  false
			if (pNode.child[index] == null || (i + 1 == word.length() && pNode.child[index].isStr == false)) {
				return false;
			}
			pNode = pNode.child[index];
		}

		return true;
	}

	/**
	 *           
	 */
	public void insert(String word) {
		if (word == null || word.isEmpty()) {
			return;
		}
		Node pNode = this.root;
		for (int i = 0; i < word.length(); i++) {
			int index = word.charAt(i) - 'a';
			if (pNode.child[index] == null) { //        ， new          
				Node tmpNode = new Node();
				pNode.child[index] = tmpNode;
			} else {

				pNode.child[index].num++; //               ， num 1，                
			}
			pNode = pNode.child[index];
		}
		pNode.isStr = true;
	}

	public Node getRoot() {
		return root;
	}

}