有道难题 之 有道搜索框 java实现

这个题目是5.29号第一场的第二题，先说句题外话，众多的参加的选手中，使用java的最终ac的人数不仅少，而且用时都比较长。尽管java可以是标准时间的3倍，不过，c/c++依然是参加这种比赛的首选。

先把题目叙述下：

描述

在有道搜索框中，当输入一个或者多个字符时，搜索框会出现一定数量的提示，如下图所示：


现在给你N个单词和一些查询，请输出提示结果，为了简化这个问题，只需要输出以查询词为前缀的并且按字典序排列的最前面的8个单词，如果符合要求的单词一个也没有请只输出当前查询词。

输入

第一行是一个正整数N，表示词表中有N个单词。
接下来有N行，每行都有一个单词，注意词表中的单词可能有重复，请忽略掉重复单词。所有的单词都由小写字母组成。
接下来的一行有一个正整数Q，表示接下来有Q个查询。
接下来Q行，每行有一个单词，表示一个查询词，所有的查询词也都是由小写字母组成，并且所有的单词以及查询的长度都不超过20，且都不为空
其中：N<=10000,Q<=10000

输出

对于每个查询，输出一行，按顺序输出该查询词的提示结果，用空格隔开。

样例输入

10
a
ab
hello
that
those
dict
youdao
world
your
dictionary
6
bob
d
dict
dicti
yo
z

样例输出

bob
dict dictionary
dict dictionary
dictionary
youdao your
z

其实，这个题，很简单，就是Trie树(字典树、前缀树)的应用；这里有一个比赛时的实现：

import java.util.ArrayList;
import java.util.Iterator;
import java.util.List;
import java.util.Map;
import java.util.Scanner;
import java.util.TreeMap;
import java.util.Map.Entry;
public class Main
{
	static class Node
	{
		Map<Character, Node> children = new TreeMap<Character, Node>();
		char ch = '0';
		boolean isWord = false;
		String word = "";
		Node(char c)
		{
			this.ch = c;
		}
		public String toString()
		{
			if (isWord)
				return word;
			else
				return "" + ch;
		}
	}
	public static void buildTrie(Node root, String str)
	{
		int strLen = str.length();
		Node base = root;
		int index = 0;
		while (true)
		{
			char c = str.charAt(index);
			Node child = base.children.get(c);
			if (child == null)
			{
				child = new Node(c);
				base.children.put(c, child);
			}
			if (index == (strLen - 1))
			{
				child.isWord = true;
				child.word = str;
				break;
			}
			index++;
			base = child;
		}
	}
	public static Node findPreNode(Node root, String str)
	{
		int strLen = str.length();
		Node base = root;
		int index = 0;
		while (true)
		{
			char c = str.charAt(index);
			Node child = base.children.get(c);
			if (child != null && index != (strLen - 1))
			{
				base = child;
				index++;
			} else
				return child;
		}
	}
	public static void findAllChildrenNode(Node root, List<Node> result,
			int size)
	{
		if (root == null || result.size() == size)
			return;
		if (root != null)
		{
			if (root.isWord && result.size() <= size)
				result.add(root);
			Iterator<Entry<Character, Node>> iter = root.children.entrySet()
					.iterator();
			while (iter.hasNext())
			{
				Node node = iter.next().getValue();
				if (result.size() < size)
					findAllChildrenNode(node, result, size);
			}
		}
	}
	/**
	 * @param args
	 */
	public static void main(String[] args)
	{
		Scanner cin = new Scanner(System.in);
		int num = cin.nextInt();
		Node root = new Node('0');
		for (int i = 0; i < num; i++)
		{
			String word = cin.next();
			buildTrie(root, word);
		}
		int sNum = cin.nextInt();
		for (int i = 0; i < sNum; i++)
		{
			String s = cin.next();
			Node node = findPreNode(root, s);
			List<Node> result = new ArrayList<Node>();
			findAllChildrenNode(node, result, 8);
			if (result.size() == 0)
			{
				System.out.println(s);
			} else
			{
				StringBuilder sb = new StringBuilder();
				for (int p = 0; p < result.size(); p++)
				{
					sb.append(result.get(p).word);
					if (p != result.size() - 1)
						sb.append(" ");
				}
				System.out.println(sb);
			}
		}
	}
}

一个基本的字典树实现，提交显示1000ms多点；杯具的是，写这个花费的时间太长了点，影响了答题；