weixin_38503891 2017-05-31 09:45 采纳率: 0%
浏览 1164
已结题

最小操作数,求帮忙解释下代码实现

以改变单词中的一个字母,同时,新产生的单词必须是在给定的单词集合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);
   }
}

}

  • 写回答

2条回答 默认 最新

  • weixin_38503891 2017-05-31 10:01
    关注

    没人?求帮忙解释下啊,来个大神

    评论

报告相同问题?

悬赏问题

  • ¥15 maple软件,用solve求反函数出现rootof,怎么办?
  • ¥50 汇编语言除法溢出问题
  • ¥65 C++实现删除N个数据列表共有的元素
  • ¥15 Visual Studio问题
  • ¥15 state显示变量是字符串形式,但是仍然红色,无法引用,并显示类型不匹配
  • ¥20 求一个html代码,有偿
  • ¥100 关于使用MATLAB中copularnd函数的问题
  • ¥20 在虚拟机的pycharm上
  • ¥15 jupyterthemes 设置完毕后没有效果
  • ¥15 matlab图像高斯低通滤波