126. Word Ladder II

我不是女神ヾ 2022-02-15 09:40 173阅读 0赞

Given two words (beginWord and endWord), and a dictionary's word list, find all shortest transformation sequence(s) from beginWord to endWord, such that:
    
    Only one letter can be changed at a time
    Each transformed word must exist in the word list. Note that beginWord is not a transformed word.
    Note:
    
    Return an empty list if there is no such transformation sequence.
    All words have the same length.
    All words contain only lowercase alphabetic characters.
    You may assume no duplicates in the word list.
    You may assume beginWord and endWord are non-empty and are not the same.
    Example 1:
    
    Input:
    beginWord = "hit",
    endWord = "cog",
    wordList = ["hot","dot","dog","lot","log","cog"]
    
    Output:
    [
      ["hit","hot","dot","dog","cog"],
      ["hit","hot","lot","log","cog"]
    ]
    Example 2:
    
    Input:
    beginWord = "hit"
    endWord = "cog"
    wordList = ["hot","dot","dog","lot","log"]
    
    Output: []
    
    Explanation: The endWord "cog" is not in wordList, therefore no possible transformation.

本题解法主要是构建一个endWord到beginWord的距离最短的单向图，然后使用回溯法得到所有答案。

public List<List<String>> findLadders(String beginWord, String endWord, List<String> wordList) {
            List<List<String>> ans = new ArrayList<>();
            if(wordList.size() == 0) return ans;
    
            //首先构建一个从从endWord到beginWord的图（只构建路径最短的）
            int min = Integer.MAX_VALUE;//min表示从beginWord到endWord的最短路径距离
            Map<String, List<String>> graph = new HashMap<>();//从beginWord到endWord的图
            Map<String, Integer> distance = new HashMap<>();//表示从beginWord出发后走的距离（没经过一个word，距离加1）
            for(String str : wordList) {//初始化
                distance.put(str, Integer.MAX_VALUE);
            }
            distance.put(beginWord, 0);
            Queue<String> queue = new ArrayDeque<>();//用队列来实现BFS以构建图
            queue.add(beginWord);
            while(!queue.isEmpty()) {
                String word = queue.poll();
                int step = distance.get(word) + 1;//表示到达endWord已经经过的距离
                if(step > min) {//如果step超过到达endWord的距离，则不将此节点加进图里
                    break;
                }
                //对word每个位置的字母进行替换来BFS
                for(int i = 0; i < word.length(); ++i) {
                    StringBuilder sb = new StringBuilder(word);
                    for(char ch = 'a'; ch <= 'z'; ++ch) {
                        sb.setCharAt(i, ch);
                        String newWord = sb.toString();
                        if(distance.containsKey(newWord)) {
                            if(step > distance.get(newWord)) {//不是到达endWord的最短路径
                                continue;
                            } else if(step < distance.get(newWord)) {
                                queue.add(newWord);
                                distance.put(newWord, step);
                            } else ;//表示该word重复变换成自己，不需处理
                            if(graph.containsKey(newWord)) {//构建单向图(反向构建，从endWord到beginWord)
                                graph.get(newWord).add(word);
                            } else {
                                List<String> list = new LinkedList<>();
                                list.add(word);
                                graph.put(newWord, list);
                            }
                            if(newWord.equals(endWord)) {//刷新从endWord到beginWord的最短距离
                                min = step;
                            }
                        }
                    }
                }
            }
    
            //使用回溯来获取结果
            LinkedList<String> current = new LinkedList<>();
            backTracking(endWord, beginWord, current, ans, graph);
            return ans;
        }
    
        private void backTracking(String word, String beginWord, List<String> current, List<List<String>> ans, Map<String, List<String>> graph) {
            if(word.equals(beginWord)) {
                current.add(0, word);
                ans.add(new ArrayList<>(current));
                current.remove(0);
                return;
            }
            current.add(0, word);
            if(graph.get(word) != null) {
                for(String str : graph.get(word)) {
                    backTracking(str, beginWord, current, ans, graph);
                }
            }
            current.remove(0);
        }

发表评论取消回复

表情：

评论列表（有 0 条评论，173人围观）

还没有评论，来说两句吧...

相关阅读

相关 LeetCode127—Word Ladder

LeetCode127—Word Ladder 原题 > Given two words (beginWord and endWord), and a dictio

女爷i/ 2022年08月22日 00:28/ 0 赞/ 118 阅读

相关 leetcode 126. Word Ladder II

Given two words (beginWord and endWord), and a dictionary's word list, find all shortest

ゝ一世哀愁。/ 2022年08月21日 02:19/ 0 赞/ 106 阅读

相关 Word Ladder--LeetCode

这道题看似一个关于字符串操作的题目，其实要解决这个问题得用图的方法。我们先给题目进行图的映射，顶点则是每个字符串，然后两个字符串如果相差一个字符则我们进行连边。接下来看看这个方

柔光的暖阳◎/ 2022年08月07日 13:54/ 0 赞/ 104 阅读

相关 leetcode 127. Word Ladder

Given two words (beginWord and endWord), and a dictionary's word list, find the length o

曾经终败给现在/ 2022年07月26日 01:41/ 0 赞/ 110 阅读

相关 leetcode 126. Word Ladder II BFS + 反向链表 + DFS

Given two words (beginWord and endWord), and a dictionary’s word list, find all shortest

怼烎@/ 2022年06月08日 05:36/ 0 赞/ 125 阅读

相关 [Leetcode][python]Word Ladder/Word Ladder II/单词接龙/单词接龙 II

Word Ladder 题目大意给定一个起始字符串和一个目标字符串，现在将起始字符串按照特定的变换规则转换为目标字符串，求最少要进行多少次转换。转换规则为每次只能

矫情吗；*/ 2022年06月04日 23:14/ 0 赞/ 169 阅读

相关 Word Ladder

LeetCode\[127. Word Ladder\] 题解难度\[medium\] 题目： Given two words (beginWo

谁践踏了优雅/ 2022年05月21日 07:18/ 0 赞/ 135 阅读

相关 LeetCode-126：Word Ladder II

题目 ![70][] 题目读起来也挺简单，有一点不太清楚，就是这个字典里不包含start，但是要包含end，其实start也不所谓吧，就是end一定要有，没有就不

不念不忘少年蓝@/ 2022年05月15日 06:56/ 0 赞/ 121 阅读

相关【LeetCode】127. Word Ladder

Word Ladder Given two words (start and end), and a dictionary, find the length of short

Bertha 。/ 2022年03月31日 10:50/ 0 赞/ 116 阅读

相关 126. Word Ladder II

Given two words (beginWord and endWord), and a dictionary's word list, find all shor

我不是女神ヾ/ 2022年02月15日 09:40/ 0 赞/ 174 阅读