单词变换

2018-05-28

题目描述：
有一个单词列表，一个初始单词和一个最终单词，初始单词需要通过单词列表逐步变换到最终单词，求变换所需的最短变换路径长度。
变换规则：每次只能变动1个字母（不可交换位置，如：从abc变成cba属于变动了2个字母），每次变换只能从单词列表中选取。
例如：初始单词hot，最终单词dog，单词列表[got, dot, god, dog, lot, log]，最短变换路径为[hot,dot,dog]，最短变换路径长度为3。
注：单词列表中包含最终单词，不包含初始单词；列表中每一项单词长度与初始单词、最终单词相同；列表中单词不重复；所有字母均为小写。

输入
输入数据有三行，第一行为初始单词；第二行为最终单词；第三行为单词列表，单词和单词之间以空格分割。

输出
最短变换路径长度。

样例输入
hot
dog
got dot god dog lot log

样例输出
3

提示
寻找最短路径相关算法。

下面是我的答案（写得不好的地方请指正哦），如果你有最好的解决方案，请在下面评论，大家一起交流学习！

import java.util.ArrayList;
import java.util.Scanner;

public class TestAgain {

    static int[][] matrix;// 邻接矩阵
    static int len;// 单词个数
    static ArrayList<Integer> path;// 单条路径记录
    static ArrayList<ArrayList<Integer>> paths;// 所有路径

    public static void main(String[] args) {
        // 接收输入参数
        Scanner scanner = new Scanner(System.in);
        String init = scanner.nextLine();
        String end = scanner.nextLine();
        String list = scanner.nextLine();
        scanner.close();
        // 将所有单词存入数组
        len = list.split(" ").length + 1;
        String[] vocabulary = new String[len];
        vocabulary[0] = init;
        int start = 0; // 最终词所在的索引
        for (int i = 1; i < len; i++) {
            vocabulary[i] = list.split(" ")[i - 1];
            if (vocabulary[i].equals(end)) {
                start = i;
            }
        }
        // 构建邻接矩阵
        matrix = nearMatrix(vocabulary);
        path = new ArrayList<Integer>();
        paths = new ArrayList<ArrayList<Integer>>();
        // 开始搜索
        look(start);
        // 寻找最短路径
        int min = Integer.MAX_VALUE;
        for (int i = 0; i < paths.size(); i++) {
            int k = paths.get(i).size();
            if (k < min && paths.get(i).get(k - 1) == 0) {
                min = k;
            }
        }
        System.out.println(min + 1);
    }

    public static void look(int start) {
        for (int i = 0; i < len; i++) {
            if (matrix[start][i] == 1 && !path.contains(i)) {
                path.add(i);
                if (i != 0) {
                    look(i);
                } else {
                    break;
                }
            }
        }
        // 添加路径
        paths.add(path);
        path = new ArrayList<Integer>();
        int length = paths.get(paths.size() - 1).size();
        for (int i = 0; i < length - 1; i++) {
            path.add(paths.get(paths.size() - 1).get(i));
        }
    }

    // 构建邻接矩阵
    public static int[][] nearMatrix(String[] vac) {
        int[][] matrix = new int[vac.length][vac.length];
        for (int i = 0; i < vac.length; i++) {
            for (int j = 0; j < vac.length; j++) {
                matrix[i][j] = compare(vac[i], vac[j]);
            }
        }
        return matrix;
    }

    // 比较两个单词是否可变换
    public static int compare(String s1, String s2) {
        int k = 0;
        for (int i = 0; i < s1.length(); i++) {
            if ((s1.charAt(i) + "").compareTo((s2.charAt(i) + "")) != 0) {
                k++;
                if (k > 1) {
                    return Integer.MAX_VALUE;
                }
            }
        }
        return k;
    }
}