字符串start每次只能改变一个字符，最终变为字符串to，返回所有的最短变换路径

提示：本题是曾经的互联网大厂校招原题，也是大厂年年必考的笔试题/面试题

本题是经典的图中的DFS+BFS结合考察最短路径的经典题目

---

文章目录

• 字符串start每次只能改变一个字符，最终变为字符串to，返回所有的最短变换路径
• • @[TOC](文章目录)
• 题目
• 一、审题
• 将list构建邻接表，然后对start到每一个点求最短距离，那个最短路径严格递增1之后到达to的路径就是最短变换路径
• • 将list构建邻接表，放入start一起构建
  • • 暴力解，找字符串的直接邻居
    • 遍历每个字符串s，让s的每个位置变a--z：26次变化，查变了的s是否在list中？
  • 然后对start到每一个点求最短距离，这个过程用BFS广播求
  • 那个最短路径严格递增1之后到达to的路径就是最短变换路径，这个过程用DFS求
  • 手撕本题的代码：将list构建邻接表，然后对start到每一个点求最短距离，那个最短路径严格递增1之后到达to的路径就是最短变换路径
• 总结

题目

字符串start每次只能改变一个字符，最终变为字符串to，变化之后的所有情况，一定在list【列表中放了所有可能的字符串】
注意：list中必然有to字符串，而且一定不重复，全部都是小写字符

请你返回所有的最短变换路径

---

一、审题

list=abc,akb, acb,abb,akc
start=abc
to=acb

abc–>abb–>acb【这是从abc变为acb的必经之路，每次只变一个字符】

你也可以这样变：
abc–>abb–>akb–>acb
但是它不是最短的变换路径

---

将list构建邻接表，然后对start到每一个点求最短距离，那个最短路径严格递增1之后到达to的路径就是最短变换路径

我们的思路就是：
（1）将list构建邻接表，
（2）然后对start到每一个点求最短距离，这个过程用BFS广播求
（3）那个最短路径严格递增1之后到达to的路径就是最短变换路径，这个过程用DFS求
现在为啥这么做你先别管？

你只管接着往下看，自然就明白了为啥我们要这么安排

将list构建邻接表，放入start一起构建

你既然要知道啥是最短的变化路径？？？
那你不构建图，找邻居，你怎么可能知道我应该变去哪里呢？？？

对吧，所以需要整一个图，方便知道start一步步去哪些邻居，然后变为to的。

既然list都是不重复的字符串，那就可以独立成一个节点，value=字符串
而abc–>abb这种，就变了一个字符串，我们认为他俩是邻居
完全可以把list抽象为图，因此，我们直接把start加入list，【to本身就在list中，不管】

然后看看每一个字符串，它经过变化一个字符，能去这个list中哪些字符串，
这样的话，在图中，我们直接让它们相连，认为都是邻居，
于是就可以做出一个所有list中字符串门邻接表了。【不过不是链表，我们把邻居放在一个list中】

比如上面那个例子：
list=abc,akb, acb,abb,akc
start已经在其中

建一个邻接表nexts：它是一个哈希表，key就是list中每一个字符串，value：list中能由key直接变一个字符来的字符串

1）abc可以直接变去哪里？a变没用，b变k：akc
c可以变b：abb
就俩吧邻居

2）看看akc又能怎么变？k变傻啥都不行，c变b：akb
好像没用别的了

3）在看abb能变啥？中间那个b变c，acb，
abb还能变akb
akb又可以变acb

基本就这样了
是不是就成型了，很容易吧

这个过程代码怎么实现呢？
也非常非常容易

暴力解，找字符串的直接邻居

每个list中的字符串都和另外N-1一个字符串一一对比，看看两者的差异就是变化一个字符，但是这样暴力就会出现o(n^2)，每个对比还需要k长度字符串匹配。
拢共o(n^2*k)复杂度
过于暴力

遍历每个字符串s，让s的每个位置变a–z：26次变化，查变了的s是否在list中？

遍历每个字符串s，让s的每个位置变a–z：26次变化，
查变了的s是否在list中？
比如abc=s
让abc的0位置，变一次a–z，26次，查list中有没有这些：
abc?bbc?cbc?dbc?ebc?……xbc?ybc?zbc?
其实abc自己就算了不要比了，最终也就变25次，
一个字符串变K次，每次对比list需要N次，每个字符串对比需要K长度
拢共o(25kNk)=o（nk^2）复杂度

往往啊，N>>k
所以呢，上面的暴力解：o(n的2次方k)>>o（nk的2次方）

懂？

手撕代码：

    //复习：
    //让abc的0位置，变一次a--z，26次，查list中有没有这些：
    //abc?bbc?cbc?dbc?ebc?……xbc?ybc?zbc?
    //其实abc自己就算了不要比了，最终也就变25次，
    //一个字符串变K次，每次对比list需要N次，每个字符串对比需要K长度
    //拢共o(25k*N*k)=o（nk^2）复杂度
    //单独一个字符，看看s变每个位置为a--z，究竟有哪些在list中？？？
    public static List<String> getNextsOfStr(String s, HashSet<String> set){
        //set里面有就加入ans
        char[] str = s.toCharArray();
        List<String> ans = new ArrayList<>();//结果，每个str--Value邻居们

        for(char ch = 'a'; ch <= 'z'; ch++){
            //26个字符，变
            for (int i = 0; i < str.length; i++) {//K个位置，每个都要变的
                if (str[i] != ch){
                    //i位置本来就是ch就不要变了
                    char tmp = str[i];//i回头要恢复，尝试别的为位置变化的情况
                    str[i] = ch;//变
                    if (set.contains(String.valueOf(str))) ans.add(String.valueOf(str));
                    str[i] = tmp;//恢复str
                }
            }
        }
        return ans;
    }

    //每次对比list需要N次，独立成一个函数
    public static HashMap<String, List<String>> writeNextsMap(List<String> list){
        HashMap<String, List<String>> nexts = new HashMap<>();
        HashSet<String> set = new HashSet<>(list);//把list转set去查，contains函数方便

        for (int i = 0; i < list.size(); i++) {
            //一个一个字符查
            nexts.put(list.get(i), getNextsOfStr(list.get(i), set));//key--value放好
        }

        return nexts;//返回邻居表，等价于图
    }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39

然后对start到每一个点求最短距离，这个过程用BFS广播求

有了上面的邻居表nexts

你不是要求最短的变换路径吗？
怎么衡量这个路径是最短的？？
那不是自然就要考量start字符串到to的最短路径吗？？？
自然就要统计，start到所有的其他的字符串的最短路径，这个嘛，自然就是图的BFS广播搜索

比如邻居表next为：

start=a，它到所有别的邻居的最短距离怎么搞？？？
a跳一步自然可以取邻居cbk，所以到cbk的距离最短就是1 1 1
从c可以取gf，自然a通过c到gf的距离最短就是2 2
通过b可以去gk，但是我们求过了，不管

这就是一个BFS广播的过程，每次都找邻居，邻居又找邻居，找过的别找了

因此，我们有哪些东西呢？？
我们有邻居表nexts，我们有start，要求start到所有图中节点的最短距离表：distancesMap表
key就是nexts中的各个邻居们，value就是start到这些个邻居的最短距离

BFS广播求最短距离的代码，手撕一波：

    //因此，我们有哪些东西呢？？
    //我们有邻居表nexts，我们有start，要求start到所有图中节点的最短距离表：distancesMap表
    //key就是nexts中的各个邻居们，value就是start到这些个邻居的最短距离
    public static HashMap<String, Integer> getLeastDistance(String start,
                                                            HashMap<String, List<String >> nexts){
        //BFS基本组件：队列
        LinkedList<String> queue = new LinkedList<>();
        queue.add(start);//一开始start开始遍历，
        //结果，就是start到所有的节点的最短路径
        HashMap<String, Integer> distanceMap = new HashMap<>();
        distanceMap.put(start, 0);//start--start的距离0

        //另外，还要标记，进入过queue，遍历过的不要走重复
        HashSet<String> set = new HashSet<>();
        set.add(start);//它经过了

        while (!queue.isEmpty()){
            //基本就是弹出操作，然后将邻居加入queue
            String cur = queue.poll();
            //看邻居
            for(String next:nexts.get(cur)){
                //cur的邻居，没经过queue的
                if (!set.contains(next)){
                    queue.add(next);
                    set.add(next);
                    //距离单算
                    distanceMap.put(next, distanceMap.get(cur) + 1);
                    //在我cur的距离之上，加1就行，就是邻居，也就是start到next的距离
                }
            }
        }

        return distanceMap;
    }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34

BFS的代码，非常非常简单的，你熟悉了基本框架，很容易就把这个代码写出来了
无非就是多一个计算距离就行了

那个最短路径严格递增1之后到达to的路径就是最短变换路径，这个过程用DFS求

稳了，咱们有了邻接表nexts
有了start，有了to
还赢了start到邻接表nexts中所有邻居的最短距离distanceMap

现在，要你计算哪些才是最短的变换路径
也就是start通过哪些邻居，变到了to呢？？
将这个变化的心里历程path，放入结果ans

举个例子：list=abc,akb, acb,abb,akc
start=abc
to=acb

path=abc–>abb–>acb【这是从abc变为acb的必经之路，每次只变一个字符】

那么，你如何才能控制这个path，它才是最短的那个变化路径呢？？？？
条件已经限制死了
你只能变化一个字符，这俩字符串必定是邻居，而start沿途要尽快到to
因此，每一次变化，距离必须严格递增，且还必须严格递增1！！！
因此，每一次变化，距离必须严格递增，且还必须严格递增1！！！
因此，每一次变化，距离必须严格递增，且还必须严格递增1！！！

下面是我记过的笔记

从abc，你要去cab，第一次，直接找abc的邻居，变1个就可以去abb
再找abb的邻居，变1个去aab，走过的别走了
再找aab的邻居，变1个去cab，每一次变化，一定是start到这个目的地字符串的距离，严格在上一次的基础上增加1
整个过程就是图上的深度优先遍历DFS，中途访问过的不要再访问了

否则就不是最短路径了？？？
除了上面的字符串路径path，还有别的可能性吗？？返回上一个邻居的时候，注意恢复现场，老油条了，恢复现场的事情，我们讲过无数遍了！！！

手撕代码实现上面的情况，最后将ans填好，有哪些path，都加入其中

    //稳了，咱们有了邻接表nexts
    //有了start=cur，有了to
    //还有了start到邻接表nexts中所有邻居的最短距离distanceMap
    //
    //现在，要你计算哪些才是最短的变换路径
    //也就是start通过哪些邻居，变到了to呢？？
    //将这个变化的心里历程path，放入结果ans
    public static void getMinPath(String cur, String to,
                                                HashMap<String, List<String>> nexts,
                                                HashMap<String, Integer> distanceMap,
                                                LinkedList<String> path, List<List<String>> ans){
        //将ans填好，就行了，外部调度会搞定这件事
        //来到cur节点的位置，必定path，就把start字符加入了，这是必经之路，如果此时cur=to，path成功了
        //path.add(cur);
        //cur到to了吗
        if (cur.equals(to)) {//貌似这玩意，需要复制一份呢？
            ans.add(new LinkedList<>(path));//path就是一个结果了，然后返回去恢复现场
        }
        else {
            //cur没有到to呢？继续递增
            //一个原则，DFS找严格递增距离为1的那些点，不能去了就是！！！
            for(String next:nexts.get(cur)){
                int dStart2cur = distanceMap.get(cur);//start--cur的距离
                //start--cur的邻居next的距离呢？
                int dStart2next = distanceMap.get(next);
                if (dStart2cur + 1 == dStart2next) {
                    path.add(next);//说明走这条next的路对了--别重复加了
                    //继续DFS
                    getMinPath(next, to, nexts, distanceMap, path, ans);
                    //然后尝试别的next可能性，需要恢复现场
                    path.pollLast();//在这清除
                }
            }
        }
    }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35

下面是我的笔记
比如，最开始a到t的距离
沿着acgt=path
得到一个结果path，加入ans
但是你还想考虑别的路径吗？？？可能还有呢?

那就恢复现场吧！path抹掉t,f,b然后
重新由a到cgt，path=acgt也可以的，加入ans
这沿途start到每一个next的距离都是cur基础上，+1严格递增1来的，这样才是最短的路径

OK？
明白了吧

手撕本题的代码：将list构建邻接表，然后对start到每一个点求最短距离，那个最短路径严格递增1之后到达to的路径就是最短变换路径

我们的思路就是：
（1）将list构建邻接表，
（2）然后对start到每一个点求最短距离，这个过程用BFS广播求
（3）那个最短路径严格递增1之后到达to的路径就是最短变换路径，这个过程用DFS求

现在，你知道，我为啥要分为这仨步骤了吗？？？
为了得到最短的那些变化路径，你要知道如何衡量start到每个邻居的距离，DFS过程中，严格递增距离1，才能是最短路径，那么你必须要准备好，strat到list中每个点的距离distanceMap
所以我们才有了步骤（2）
BFS广播求start到各个点的距离，必然知道strat开始它邻居是谁？
这就引出了必然的（1）步骤

懂？

现在我们来手撕整个大流程，拿到list，start，to，求出start到to的路径就是最短变换路径

    //现在我们来手撕整个大流程，拿到list，start，to，求出start到to的路径就是最短变换路径
    public static List<List<String>> writeAllMinPaths(List<String > list, String start, String to){
        //（1）将list构建邻接表，
        list.add(start);//为了防止重复，加入set去重——下面内部走
        HashMap<String, List<String>> nexts = writeNextsMap(list);
        //（2）然后对start到每一个点求最短距离，这个过程用BFS广播求
        HashMap<String, Integer> distanceMap = getLeastDistance(start, nexts);
        //（3）那个最短路径严格递增1之后到达to的路径就是最短变换路径，这个过程用DFS求
        //稳了，咱们有了邻接表nexts
        //有了start=cur，有了to
        //还有了start到邻接表nexts中所有邻居的最短距离distanceMap
        //现在，要你计算哪些才是最短的变换路径
        //也就是start通过哪些邻居，变到了to呢？？
        //将这个变化的心里历程path，放入结果ans
        List<List<String>> ans = new ArrayList<>();
        LinkedList<String> path = new LinkedList<>();
        getMinPath(start, to, nexts,distanceMap, path, ans);
        
        return ans;//最终ans搞定了
    }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

测试一把：

    public static void test(){
        String start = "abc";
        String end = "cab";
        List<String> list = new ArrayList<>();
        list.add("cab");
        list.add("acc");
        list.add("cbc");
        list.add("ccc");
        list.add("cac");
        list.add("cbb");
        list.add("aab");
        list.add("abb");

        List<List<String>> ans = findMinPath(start, end, list);
        for (List<String> path:ans){
            for(String str:path) System.out.print(str +"-->");
            System.out.println();
        }


        System.out.println();
        ans = writeAllMinPaths(list, start, end);//end=to
        for (List<String> path:ans){
            for(String str:path) System.out.print(str +"-->");
            System.out.println();
        }
    }

    public static void main(String[] args) {
        test();
    }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31

问题不大，刺激

abb-->aab-->cab-->
abb-->cbb-->cab-->
cbc-->cac-->cab-->
cbc-->cbb-->cab-->

abb-->aab-->cab-->
abb-->cbb-->cab-->
cbc-->cac-->cab-->
cbc-->cbb-->cab-->
1
2
3
4
5
6
7
8
9

老牛逼了！！！
绝对让你的BFS，DFS，透彻理解通
另外还搞了一道图的算法题

笔试基本不考图，面试也很少，但是一旦考到，你不会就炸了
因此学过本题，理解通透，应对互联网大厂的面试，再遇到这类题目问题也就不大了。

---

总结

提示：重要经验：

1）将list构建邻接表，然后对start到每一个点求最短距离，这个过程用BFS广播求，那个最短路径严格递增1之后到达to的路径就是最短变换路径，这个过程用DFS求
2）本题是曾经的互联网大厂校招原题，也是大厂年年必考的笔试题/面试题
3）笔试求AC，可以不考虑空间复杂度，但是面试既要考虑时间复杂度最优，也要考虑空间复杂度最优。