以改变单词中的一个字母，同时，新产生的单词必须是在给定的单词集合Dict中。求所有行得通步数最少的修改方法。
举个例子如下：
Given:
A = "hit"
B = "cog"
Dict = ["hot","dot","dog","lot","log"]
Return
[
["hit","hot","dot","dog","cog"],
["hit","hot","lot","log","cog"]
]
即把字符串A = "hit"转变成字符串B = "cog"，有以下两种可能：
- "hit" -> "hot" -> "dot" -> "dog" -> "cog"；
- "hit" -> "hot" -> "lot" -> "log" ->"cog"。
答题说明:
- A和B相同的情况下不需要做转换，此时直接返回空集；
- main函数是为方便你在提交代码之前进行在线编译测试，可不完成。
import java.util.HashSet;import java.util.Map;import java.util.Set;import java.util.TreeSet;import java.util.Vector;import java.util.Collections;import java.util.Comparator;public class Solution { class TreeNode{ String src; Vector passNodes; HashSet passNodeSrcs; public TreeNode(String src, TreeNode parent){ this.src = src; passNodes = new Vector (); if(parent != null){ passNodes.addAll(parent.passNodes); } passNodes.add(src); passNodeSrcs = new HashSet (); if(parent != null){ passNodeSrcs.addAll(parent.passNodeSrcs); } passNodeSrcs.add(src); } public boolean equals(String src){ return this.src.equals(src); } } public boolean isOneDiff(String src, String dest){ int diffCount = 0; for(int i = 0; i < src.length(); i++){ if(src.charAt(i) != dest.charAt(i)){ diffCount++; if(diffCount > 1){ return false; } } } return diffCount == 1; } public void buildTree(TreeNode node, String end, Set dict, Vector > results){ if(isOneDiff(node.src, end)){ node.passNodes.add(end); results.add(node.passNodes); return; } for(String d : dict){ if(node.passNodeSrcs.contains(d)){ continue; } if(!isOneDiff(node.src, d)){ continue; } TreeNode child = new TreeNode(d, node); buildTree(child, end, dict, results); } } public Vector > findLadders(String start, String end, Set dict) { Vector > results = new Vector >(); // 相同不转换 if(start.equals(end)){ return results; } // 建树计算 TreeNode node = new TreeNode(start, null); buildTree(node, end, dict, results); // 取最短的 int min = dict.size() + 2; for(Vector result : results){ if(result.size() < min){ min = result.size(); } } Vector > resultAll = new Vector >(); for(Vector result : results){ if(result.size() == min){ resultAll.add(result); } } return resultAll; } //start 提示：自动阅卷起始唯一标识，请勿删除或增加。 public static void main(String[] args) { String start = "hit"; String end = "cog"; Set dict = new HashSet (); dict.add("hot"); dict.add("dot"); dict.add("dot"); dict.add("dog"); dict.add("lot"); dict.add("log"); Vector > results = new Solution().findLadders(start,end,dict); for(Vector vect : results){ System.out.println(vect); } } //end 提示：自动阅卷结束唯一标识，请勿删除或增加。}