我必须实现 T9 Dictionary 。
本质上，当我按下 9 个键中的任何一个时，它应该向我显示可以使用该组合键开始的前 5 个单词。
如果我输入“46”，它可以给出“酒店”或“好”，这取决于我在按 4 时是打算输入“g”还是“h”。
优先级取决于哪些词相对流行——例如，您可以使用前100 000 个词中的前 5000 个词。
我正在做的代码是：
进口
import java.io.BufferedReader;
import java.io.File;
import java.io.FileReader;
import java.util.Date;
import java.util.HashMap;
import java.util.LinkedList;
import java.util.List;
import java.util.Map;
T9Dict 类
public class T9Dict {
private static final Runtime s_runtime = Runtime.getRuntime();
public static void main(String[] args) throws Exception {
runGC();
long heap1 = usedMemory();
long start = new Date().getTime();
Trie trie = Trie.getInstance();
System.out.println("Creating Dictionary");
File f = new File("C:\\Users\\hp1\\Desktop\\100kfound.txt");
BufferedReader br = new BufferedReader(new FileReader(f));
String s = br.readLine();
int i = 0;
do {
i++;
trie.add(s);
s = br.readLine();
} while (s != null);
br.close();
long end = new Date().getTime();
long time = (end - start);
System.out.println("Loaded Dictionary with " + i + " words in " + time
+ " msec");
// runGC();
long heap2 = usedMemory(); // take an "after" heap snapshot:
System.out.println("Memory used = " + (heap2 - heap1));
String pattern = "4663";
start = new Date().getTime();
String word = trie.getWord(pattern);
end = new Date().getTime();
time = (end - start);
System.out.println("Found word : " + word + " in " + time + " msec");
}
private static void runGC() throws Exception {
// for whatever reason it helps to call Runtime.gc()
// using several method calls:
for (int r = 0; r < 4; ++r) {
_runGC();
}
}
private static void _runGC() throws Exception {
long usedMem1 = usedMemory();
long usedMem2 = Long.MAX_VALUE;
for (int i = 0; (usedMem1 < usedMem2) && (i < 1000); ++i) {
s_runtime.runFinalization();
s_runtime.gc();
Thread.currentThread().yield();
usedMem2 = usedMem1;
usedMem1 = usedMemory();
}
}
private static long usedMemory() {
return s_runtime.totalMemory() - s_runtime.freeMemory();
}
}
特里类
class Trie {
private static final String regex = "[a-zA-Z]*";
private static Trie instance = null;
Node root = null;
Map<Character, Integer> map = new HashMap<Character, Integer>();
private Trie() {
map.put('a', 2);
map.put('b', 2);
map.put('c', 2);
map.put('d', 3);
map.put('e', 3);
map.put('f', 3);
map.put('g', 4);
map.put('h', 4);
map.put('i', 4);
map.put('j', 5);
map.put('k', 5);
map.put('l', 5);
map.put('m', 6);
map.put('n', 6);
map.put('o', 6);
map.put('p', 7);
map.put('q', 7);
map.put('r', 7);
map.put('s', 7);
map.put('t', 8);
map.put('u', 8);
map.put('v', 8);
map.put('w', 9);
map.put('x', 9);
map.put('y', 9);
map.put('z', 9);
}
private int getVal(char c) {
return map.get(c);
}
public static Trie getInstance() {
if (instance == null) {
synchronized (Trie.class) {
instance = new Trie();
}
}
return instance;
}
public String getWord(String pattern) {
String s = null;
Node node = root;
int i = 0;
int num = 0;
while (i < pattern.length()) {
num = pattern.charAt(i) - '0';
if (num == node.val) {
i++;
if (i == pattern.length()) {
s = node.list.get(0);
}
node = node.middle;
} else if (num < node.val) {
if (i == pattern.length()) {
s = node.list.get(0);
}
node = node.left;
} else {
if (i == pattern.length()) {
s = node.list.get(0);
}
node = node.right;
}
}
return s;
}
public void add(String s) {
if (s.length() > 0) {
s = s.toLowerCase();
System.out.println("Adding : " + s);
if (root == null) {
root = new Node(this.getVal(s.charAt(0)));
Node node = root;
Node temp = null;
for (int i = 1; i < s.length(); i++) {
temp = new Node(getVal(s.charAt(i)));
node.middle = temp;
node = temp;
if (i == s.length() - 1) {
temp.set(s);
}
}
} else {
Node node = root;
int i = 0;
Node temp = null;
int val = 0;
while (i < s.length()) {
val = getVal(s.charAt(i));
if (node.val == val) {
if (i == s.length() - 1) {
node.set(s);
i++;
} else {
i++;
if (node.middle == null) {
while (i < s.length()) {
val = getVal(s.charAt(i));
temp = new Node(val);
node.middle = temp;
node = temp;
if (i == s.length() - 1) {
temp.set(s);
}
i++;
}
} else {
node = node.middle;
}
}
} else if (val < node.val) {
if (node.left == null) {
temp = new Node(val);
node.left = temp;
node = temp;
if (i == s.length() - 1) {
temp.set(s);
} else {
i++;
while (i < s.length()) {
val = getVal(s.charAt(i));
temp = new Node(val);
node.middle = temp;
node = temp;
if (i == s.length() - 1) {
temp.set(s);
}
i++;
}
}
} else {
node = node.left;
}
} else {
if (node.right == null) {
temp = new Node(val);
node.right = temp;
node = temp;
if (i == s.length() - 1) {
temp.set(s);
} else {
i++;
while (i < s.length()) {
val = getVal(s.charAt(i));
temp = new Node(val);
node.middle = temp;
node = temp;
if (i == s.length() - 1) {
temp.set(s);
}
i++;
}
}
} else {
node = node.right;
}
}
}
}
}
}
}
节点类
class Node {
int val;
Node left;
Node middle;
Node right;
List<String> list = new LinkedList<String>();
public Node(int val) {
this.val = val;
}
public void set(String s) {
list.add(s);
}
public String toString() {
return String.valueOf(val);
}
}
添加到 Trie 时，此代码给出 nullpointerexception 我找不到解决方案，请帮助