单词查找之Trie树

单词查找之Trie树

题目：

• 输入：
  输入的第一行为一个正整数n，表示词典的大小，其后n行，每一行一个单词（不保证是英文单词，也有可能是火星文单词哦），单词由不超过10个的小写英文字母组成，可能存在相同的单词，此时应将其视作不同的单词。接下来的一行为一个正整数m，表示询问的次数，其后m行，每一行一个字符串，该字符串由不超过10个的小写英文字母组成，表示一个询问。

• 输出：
  对于每一个询问，输出一个整数Ans,表示词典中以小Hi给出的字符串为前缀的单词的个数。

样例输入：
5
babaab
babbbaaaa
abba
aaaaabaa
babaababb
5
babb
baabaaa
bab
bb
bbabbaab
样例输出：
1
0
3
0
0

上图为一个Trie树，使用java实现该树，并完成上面的题目要求：

import java.util.LinkedList;
import java.util.Scanner;public class Trie {private Node root;public Trie(){root = new Node(' ');}public void insert(String word){Node current = root;for (int i=0; i < word.length(); i++){Node child = SubNodeByConent(word.charAt(i));if (child != null){current = child;}else{current.childList.add(new Node(word.charAt(i)));current = SubNodeByConent(word.charAt(i));}//写在这里表示重复单词也应该加一unt++;  }current.isEnd = true;}//查找单词public Node search(String word){Node current = root;for (int i = 0; i < word.length(); i++){if (SubNodeByConent(word.charAt(i)) == null){return null;}else{current = SubNodeByConent(word.charAt(i));}}if (current.isEnd == true) return current;else return null;}//查找前缀public Node searchPre(String word){Node current = root;for (int i = 0; i < word.length(); i++){if (SubNodeByConent(word.charAt(i)) == null){return null;}else{current = SubNodeByConent(word.charAt(i));}}return current;}public void deleteWord(String word){if (search(word) == null) return;Node current = root;for (char c : CharArray()){Node child = SubNodeByConent(c);if (unt == 1){ve(child);return;}else {unt--;current = child;}}current.isEnd = false;}private class Node{char content;                   //节点中存储的字母boolean isEnd;                  //是否是一个单词的末尾节点int count;                      //以当前节点和当前节点到根节点路径上的所有节点为前缀的单词的数目LinkedList<Node> childList;     //当前节点的子节点public Node(char c){content = c;childList = new LinkedList<Node>();isEnd = false;count = 0;}public Node getSubNodeByConent(char c){for (Node childNode: childList){if (t == c){return childNode;}}return null;}   }public static void main(String [] str){Trie trie = new Trie();Scanner in = new Scanner(System.in);int wordCount = in.nextInt();while (wordCount > 0){String word = in.next();trie.insert(word);wordCount--;}int searchCount = in.nextInt();while (searchCount > 0){String searchWord = in.next();if (trie.searchPre(searchWord) == null){System.out.println(0);}else{Node resultNode = trie.searchPre(searchWord);System.out.unt);}searchCount--;}}}