这是一道我之前去腾讯面试机器学习岗位时候碰到的面试题。将从以下几点进行描述：
1.问题描述
2.思路
3.源码
4.应用
1.问题描述
Question.现在有一本英文单词词典，里面大概放了2万个英文单词，这些单词全部由26个字母组成，现在提供一个基本操作，它可以是：
1) 增加一个字母：ear-->bear 2) 删除一个字母：down-->own 3) 修改一个字母：apple-->apply 三种中的任何一种。 下面，我随便从2万个单词中拿两个单词出来，请告诉我该如何通过最少次数的基本操作从第一个词变成第二个词，并且，每次基本操作后得到的新单词需要存在于词典中，即必须每步都是合法词汇，如果无法转换过去也需要告诉我，请帮我设计一个方案。（例如：age->bage->bag->big->pig，每一个单词都存在于词典中）
2.思路：
1.很多做文本的人可能会想到字典树，但是那个只能解决单词匹配问题，而这个问题属于类似社交网络的问题，因此不要绕进去那个思维里。
2.使用无向图结构来保存所有的单词，结合Levenshtein距离（最小编辑距离）来表征单词之间的可转换关系，关于Levenshtein距离的算法和思路，我会在另外一篇文章中介绍，这里简单来说就是一个字符串通过上述3种简单变换后得到另外一个字符串过程中经历的变换次数。
3.采取动态规划的方式去寻找图中两节点间的最短距离，但是这个情景中，节点若相邻则是双向的，并且只要相连那么距离都为1，因此可以直接选择BFS，即图的广度优先遍历来寻找一个节点到另外一个节点的最短路径。
3.源码
下面直接展示源码：
package com.zzz.DictionarySearch; import java.io.BufferedReader; import java.io.FileInputStream; import java.io.IOException; import java.io.InputStreamReader; import java.nio.charset.Charset; import java.util.ArrayList; import java.util.HashMap; import java.util.HashSet; import java.util.LinkedList; import java.util.List; import java.util.Queue; import java.util.Set; /** * @author zzzzhuang * Abstract：使用无向图结合最小编辑距离来保存单词和它们之间可转换的关系 */ public class GraphDic { private static String CharSet = "UTF-8"; public HashMap<String, GraphNode> nodes = new HashMap<String, GraphNode>(); //词-节点一一对应的map /** * 从本地文件初始化字典网络图 * @param path */ public GraphDic(String path) { BufferedReader br=null; try { br = new BufferedReader(new InputStreamReader(new FileInputStream(path), Charset.forName(CharSet))); String line=null; while ((line=br.readLine())!=null) { line=line.trim(); if (line.equals("")) { //跳过空行 continue; } if (!addNode(line)) { System.err.println("添加不成功："+line); } } } catch (IOException e) { System.err.println("reader load failed"); e.printStackTrace(); } finally { if (br!=null) { try { br.close(); } catch (IOException e) { System.err.println("reader close failed"); e.printStackTrace(); } } } } /** * 添加节点 * @param word * @return */ public boolean addNode(String word) { //if word 存在 if (nodes.containsKey(word)) { System.err.print("单词已存在->"); return false; } //if word 不存在 if (nodes.isEmpty()) { //首次添加，容器为空 nodes.put(word, new GraphNode(word)); return true; } else { //二次添加，容器不为空 GraphNode newNode = new GraphNode(word); for (GraphNode node: nodes.values()) { int distance = LevenshteinDistance.distance(word, node.word); if (distance==1) { //节点相邻 newNode.addNeighbour(node); node.addNeighbour(newNode); } else if (distance<=0) { System.err.print("编辑距离计算有误:"+word+" 与 "+node.word+"->"); return false; } } nodes.put(word, newNode); return true; } } /** * 打印图的邻接列表 */ public void showGraph() { System.out.println("收录词汇："+nodes.size()); int index=0; for (GraphNode node: nodes.values()) { System.out.print("No."+index+": "+node.word+"->"); List<GraphNode> neighbours=node.adjacentNodes; if (neighbours==null) { System.out.println("null"); continue; } for (int i = 0; i < neighbours.size(); i++) { System.out.print(neighbours.get(i).word+" "); } System.out.println(); index++; } } /** * 单词寻迹 * @param src * @param dst * @return */ public Report searchPath(String src, String dst) { if (nodes.get(src).adjacentNodes==null || nodes.get(dst).adjacentNodes==null) { //如果其中有一个是孤立节点则不可能有路径 return new Report(false, null); } else { return find(src, dst); } } /** * 寻迹核函数 * @param word 起始词 * @param target 目标词 * @return 结果 */ private Report find(String word, String target) { HashSet<GraphNode> visitedNodes=new HashSet<GraphNode>(); GraphNode wordNode=nodes.get(target); GraphNode targetNode=nodes.get(word); Queue<GraphNode> queue = new LinkedList<GraphNode>(); queue.offer(wordNode); while (!queue.isEmpty()) { GraphNode curNode = queue.poll(); if (!curNode.visited) { curNode.visited=true; visitedNodes.add(curNode); if (curNode.equals(targetNode)) { //注意：==与equal的区别 resetStates(visitedNodes); return new Report(true, curNode); } List<GraphNode> neighbours = curNode.adjacentNodes; //把 for (GraphNode e : neighbours) { if (!e.visited) { e.fatherNode=curNode; } queue.offer(e); } } } resetStates(visitedNodes); return new Report(false, null); } /** * 重置已访问的图节点 * @param resets 已访问点集 */ private void resetStates(Set<GraphNode> resets) { for (GraphNode node : resets) { node.visited=false; } } /** 测试 */ public static void main(String[] args) { GraphDic dicGrahp = new GraphDic("data/test.txt"); dicGrahp.showGraph(); Report result = dicGrahp.searchPath("rid", "abcd"); System.out.println(result); } } /** * 图节点类 * @author zzzzhuang */ class GraphNode { public String word=null; //数据：单词 public boolean visited=false; //是否已访问 public boolean found=false; //是否目标节点 public List<GraphNode> adjacentNodes = null; //邻接列表 public GraphNode fatherNode=null; //父节点：循迹回溯 public GraphNode(String word) { this.word=word; } /** * 添加邻节点 * @param node 邻节点 */ public void addNeighbour(GraphNode node) { if (adjacentNodes==null) { adjacentNodes=new ArrayList<GraphNode>(); } adjacentNodes.add(node); } @Override public int hashCode() { return word.hashCode(); } @Override public boolean equals(Object obj) { if (obj instanceof GraphNode) { GraphNode node = (GraphNode) obj; if (node.word.equals(word)) { return true; } else { return false; } } else { return false; } } } /** * 返回结果类 * @author zzzzhuang */ class Report { public GraphNode targetGraphNode; //目标节点 public boolean result=false; //是否寻迹成功 public Report(boolean res, GraphNode targetNode) { result=res; targetGraphNode=targetNode; } @Override public String toString() { StringBuffer buffer=new StringBuffer(); buffer.append("是否可行:").append(result).append(" 策略:"); if (targetGraphNode==null) { buffer.append("null"); } else { GraphNode node=targetGraphNode; while (node.fatherNode!=null) { buffer.append(node.word).append("->"); node=node.fatherNode; } buffer.append(node.word); } return buffer.toString(); } }
上述代码中定义了GraphNode作为图中的节点类，在GraphNode类中定义visited来避免重复，并使用邻接列表来保存每个节点的所有邻节点，此外为了回溯路径，定义了一个父节点类用来保存来路，在找到目标单词后可沿着父节点依次回溯来获取完整路径。外围则使用HashMap来保存用户传入的String类型单词与图节点的一一对应关系。
关于这类简单模型进行升华后其实可以来解决以下两类实际应用问题：
1.社交网络中可能认识的人，即好友推荐。你的好友都是与你距离为1的人，而与其距离为1的人则是与你距离为2的人，再综合你们的其他特征，将作为推荐的候选人。
2.社交网络找人，俗话说任何两个人之间都可以通过6个人的搭桥来产生联系，那么如果掌握了足够的信息，就可以构建基于图的社交网络，如果你想联系某个领域的某个目标人物，你需要做的则是在这个社交图网络中寻找最短路径，来达到目的。
