以改变单词中的一个字母,同时,新产生的单词必须是在给定的单词集合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<String> passNodes;
HashSet<String> passNodeSrcs;
public TreeNode(String src, TreeNode parent){
this.src = src;
passNodes = new Vector<String>();
if(parent != null){
passNodes.addAll(parent.passNodes);
}
passNodes.add(src);
passNodeSrcs = new HashSet<String>();
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<String> dict, Vector<Vector<String>> 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<Vector<String>> findLadders(String start, String end, Set<String> dict) {
Vector<Vector<String>> results = new Vector<Vector<String>>();
// 相同不转换
if(start.equals(end)){
return results;
}
// 建树计算
TreeNode node = new TreeNode(start, null);
buildTree(node, end, dict, results);
// 取最短的
int min = dict.size() + 2;
for(Vector<String> result : results){
if(result.size() < min){
min = result.size();
}
}
Vector<Vector<String>> resultAll = new Vector<Vector<String>>();
for(Vector<String> result : results){
if(result.size() == min){
resultAll.add(result);
}
}
return resultAll;
}
public static void main(String[] args) {
String start = "hit";
String end = "cog";
Set<String> dict = new HashSet<String>();
dict.add("hot");
dict.add("dot");
dict.add("dot");
dict.add("dog");
dict.add("lot");
dict.add("log");
Vector<Vector<String>> results = new Solution().findLadders(start,end,dict);
for(Vector<String> vect : results){
System.out.println(vect);
}
}
}