记一道未能答出的算法面试题
记一道未能答出的算法面试题
昨天晚上，参加了一场面试，有道算法题当时没答出来，痛心疾首！刚刚起床给娃娃换尿布的空当，突然间就想清楚了实现的办法，当时没答出来就是卡在构建多叉树这一点！本文会给出这个问题的解答，同时反思为什么没答出来，以期为以后的面试提供一些借鉴。
一、题目
任务：查词典
描述：有一个词典文件，每行一个词。编写程序在用户输入的一段文本中，找到所有在字典中的词，优先匹配最长的词，并在句子中标记出来。要求尽量少的使用内存，速度尽量快。
输入：
- 词典文件，假设有这些词：杭州 西湖 西湖博物馆 博物馆
- 用户输入的一段文字，如“我在杭州西湖边的西湖博物馆里面。”
输出：
一个字符串，词典中的词单独分出来，并在后面带上标记，如：“我在 杭州/W 西湖/W 边的 西湖博物馆/W 里面。”
二、分析与作答
这道题要分两步来解答，首先，利用词典文件，在内存中构建一个单词查找树；其次，遍历用户输入，实时在单词查找树中查找，匹配到一个最长的单词时，按照格式输出。所以，首先来构建树，第一步自然是定义Node类：
class Node {
public Character ch = null;
public boolean isWordEnd = false;
public Map<Character, Node> next;
public Node() {
this.next = new HashMap<>(); }
public Node(char ch) {
this.ch = ch;
this.next = new HashMap<>(); }
public Node(char ch, boolean isWordEnd) {
this.ch = ch;
this.isWordEnd = isWordEnd;
this.next = new HashMap<>();
}}/*以上是定义了一个节点类， 在一个节点类中，首先要存储这个节点中的字符， 所以定义了ch这个成员变量；同时要存储这个节点 下面的节点们，为了提高查找效率，使用了Map， 其key即是该节点下面的一个节点中的字符，value就是这个下面的节点。 看起来，下面的节点中的字符数据在key和value中都存在，有点浪费空间， 但这是典型的以空间换时间的策略，后续在使用查找树时会有感觉。 */
下一步，我们要定义词典类，该类根据单词文件，利用上面的Node类，构建一个单词查找树，并使用它进行查询。
import java.util.HashMap;
import java.util.Map;
public class Dictionary {
public Node root = new Node();
public void generateDic(String[] dicFile) {
for (int i = 0; i < dicFile.length; i++) {
Map<Character, Node> cur = root.next;
Node curNode = null;
char[] chs = dicFile[i].toCharArray();
for (int j = 0; j < chs.length; j++) {
if (cur.containsKey(chs[j])) {
curNode = cur.get(chs[j]);
cur = cur.get(chs[j]).next;
} else {
Node addNode = new Node(chs[j]);
cur.put(chs[j], addNode);
curNode = addNode;
cur = addNode.next;
}
if(j == chs.length-1){
curNode.isWordEnd = true;
}
}
}
}
public static void main(String[] args) {
Dictionary dic = new Dictionary();
String[] dicFile ={"杭州", "西湖", "西湖博物馆"};
dic.generateDic(dicFile);
char[] input = "我在杭州西湖博边的西湖博物馆里面".toCharArray();
Map<Character, Node> cur = dic.root.next;
boolean inWord = false;
int wordHead = -1;
int wordEnd = -1;
for (int i = 0; i < input.length; i++) {
if (inWord == false) {
cur = dic.root.next;
wordHead = -1;
wordEnd = -1;
if (cur.containsKey(input[i])) {
inWord = true;
wordHead = i;
if(cur.get(input[i]).isWordEnd == true)
wordEnd = i;
cur = cur.get(input[i]).next;
} else {
System.out.print(input[i]);
}
} else {
if (cur.containsKey(input[i])) {
if(cur.get(input[i]).isWordEnd == true)
wordEnd = i;
cur =cur.get(input[i]).next;
} else {
if(wordEnd == -1){
i = wordHead;
inWord = false;
continue;
}else{
System.out.print(" ");
printWord(input, wordHead, wordEnd);
System.out.print("/W");
i = wordEnd;
inWord = false;
continue;
}
}
}
if(i == input.length-1 && inWord == true){
if(wordEnd != -1){
System.out.print(" ");
printWord(input, wordHead, wordEnd);
System.out.print("/W");
i = wordEnd;
inWord = false;
}else{
i = wordHead;
inWord = false;
}
}
}
}
private static void printWord(char[] input, int wordHead, int wordEnd) {
for(int i = wordHead; i <= wordEnd; i++)
System.out.print(input[i]);
} }//该程序的输出为：
//我在 杭州/W 西湖/W博边的 西湖博物馆/W里面在上面的main方法中，使用单词查找树时，我们大量使用了containsKey这一方法，由于该方法属于Map，所以其查找效率为O(1)。这使得我们处理N个字符的字符串时，时间复杂度降到了O(N)。
三、总结与反思
认真看看上面的解答，其实并不算难。自己为什么没有答出来呢？分析来分析去，还是因为练得少，手生。面试前，近半年时间，虽然在工作，但是算法类的题目几乎没有练习过，中午得知晚上面试时，才在下午工作空隙中将排序动规之类粗略回忆了一下。
真正动起手来开始写代码，才发现手生的不行，看到这个题目，虽然大致知道用单词查找树，可是却无法创建出来，导致无法完成解答。
以后面试，尤其是代码类的面试，一定要留出几天，认真找几道题练练手，达到warm up的效果后再去面试，不能就这样赤膊上阵了。