昨天晚上，参加了一场面试，有道算法题当时没答出来，痛心疾首！刚刚起床给娃娃换尿布的空当，突然间就想清楚了实现的办法，当时没答出来就是卡在构建多叉树这一点！本文会给出这个问题的解答，同时反思为什么没答出来，以期为以后的面试提供一些借鉴。

一、题目

任务：查词典
描述：有一个词典文件，每行一个词。编写程序在用户输入的一段文本中，找到所有在字典中的词，优先匹配最长的词，
并在句子中标记出来。要求尽量少的使用内存，速度尽量快。

输入：

1. 词典文件，假设有这些词：杭州 西湖 西湖博物馆 博物馆
2. 用户输入的一段文字，如“我在杭州西湖边的西湖博物馆里面。”

输出：一个字符串，词典中的词单独分出来，并在后面带上标记，如：“我在 杭州/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的效果后再去面试，不能就这样赤膊上阵了。