• 微信公众号:美女很有趣。 工作之余,放松一下,关注即送10G+美女照片!

126. 单词接龙 II

开发技术 开发技术 3小时前 2次浏览

题目

按字典 wordList 完成从单词 beginWord 到单词 endWord 转化,一个表示此过程的 转换序列 是形式上像 beginWord -> s1 -> s2 -> … -> sk 这样的单词序列,并满足:

  • 每对相邻的单词之间仅有单个字母不同。
  • 转换过程中的每个单词 si(1 <= i <= k)必须是字典 wordList 中的单词。注意,beginWord 不必是字典 wordList 中的单词。
  • sk == endWord

给你两个单词 beginWord 和 endWord ,以及一个字典 wordList 。请你找出并返回所有从 beginWord 到 endWord 的 最短转换序列 ,如果不存在这样的转换序列,返回一个空列表。每个序列都应该以单词列表 [beginWord, s1, s2, …, sk] 的形式返回。

示例 1:
输入:beginWord = “hit”, endWord = “cog”, wordList = [“hot”,”dot”,”dog”,”lot”,”log”,”cog”]
输出:[[“hit”,”hot”,”dot”,”dog”,”cog”],[“hit”,”hot”,”lot”,”log”,”cog”]]
解释:存在 2 种最短的转换序列:
“hit” -> “hot” -> “dot” -> “dog” -> “cog”
“hit” -> “hot” -> “lot” -> “log” -> “cog”

示例 2:
输入:beginWord = “hit”, endWord = “cog”, wordList = [“hot”,”dot”,”dog”,”lot”,”log”]
输出:[]
解释:endWord “cog” 不在字典 wordList 中,所以不存在符合要求的转换序列。

提示:
1 <= beginWord.length <= 7
endWord.length == beginWord.length
1 <= wordList.length <= 5000
wordList[i].length == beginWord.length
beginWord、endWord 和 wordList[i] 由小写英文字母组成
beginWord != endWord
wordList 中的所有单词 互不相同

BFS+DFS

126. 单词接龙 II

题目要我们找 最短转换序列,提示我们需要使用 广度优先遍历广度优先遍历就是用于找无权图的最短路径

与绝大多数使用广度优先遍历,只要求我们返回最短路径是多少的问题(本题的前置问题 127. 单词接龙 )相比,本题要求返回 所有 从 beginWord 到 endWord 的最短转换序列,提示我们需要使用搜索算法(回溯算法、深度优先遍历)完成

难点和注意事项
需要注意的是,由于要找最短路径,连接 dot 与 lot 之间的边就不可以被记录下来,同理连接 dog 与 log 之间的边也不可以被记录。这是因为经过它们的边一定不会是最短路径。因此在广度优先遍历的时候,需要记录的图的关系如下图所示。

126. 单词接龙 II

由于位于广度优先遍历同一层的单词如果它们之间有边连接,不可以被记录下来。因此需要一个哈希表记录遍历到的单词在第几层。理解下面这张图和图中的说明非常重要。

126. 单词接龙 II

这样我们的大致思路也就出来了:

(1)首先在BFS的过程中记录下”hit“到”cog“路径中每个结点的后继结点,这一部分是解决这道题的关键。对于上图,记录的后继关系有:

hit: hot

hot: dot, lot

dot: dog

lot: log

dog: cog

log: cog

具体做法是使用一个哈希表记录遍历到的单词在第几层,当选择后继结点时后继结点必须是在当前结点的下一层。使用一个boolean类型的变量记录是否已经遍历到了endWord所在的层,如果是则在遍历完这一层之后跳出while循环。

(2)根据记录下来的后继关系,使用DFS找到所有“hit”到“cog”的路径。因为后继关系是最短路径下的,所有DFS找到的所有路径都是最短路径。

    Map<String,List<String>> map=new HashMap<>();
    List<List<String>> res=new ArrayList<>();
    //map已经记录了每个结点的后继结点,找到起始结点到目标结点的所有路径
    private void dfs(String endWord,String word,List<String> path){
        if(word.equals(endWord)){
            res.add(new ArrayList<String>(path));
            return;
        }
        if(!map.containsKey(word)) return;
        List<String> nextWords=map.get(word);
        for(String nextWord:nextWords){
            path.add(nextWord);
            dfs(endWord,nextWord,path);
            path.remove(path.size()-1);
        }
    }
    //判断两个字符串是否刚好只有一个字符不一样
    private boolean isNeighbor(String word,String nextWord){
        int cnt=0;
        for(int i=0;i<word.length();++i){
            if(word.charAt(i)!=nextWord.charAt(i)){
                cnt++;
                if(cnt>1) return false;
            }
        }
        return cnt==1;
    }
    public List<List<String>> findLadders(String beginWord, String endWord, List<String> wordList) {
        Map<String,Integer> levels=new HashMap<>();
        levels.put(beginWord,1);
        Queue<String> q=new LinkedList<>();
        q.offer(beginWord);
        boolean found=false;
        int level=0;
        //找到转换序列中每个结点的后继结点
        while(!q.isEmpty()){
            int n=q.size();
            level++;
            for(int i=0;i<n;++i){
                String word=q.poll();
                List<String> list=new ArrayList<>();
                for(String newWord:wordList){
                    if((!levels.containsKey(newWord)||levels.get(newWord)==level)&&isNeighbor(word,newWord)){
                        levels.put(newWord,level);
                        q.offer(newWord);
                        list.add(newWord);
                        if(newWord.equals(endWord)) found=true;
                    }
                }
                map.put(word,list);
            }
            if(found) break;
        }
        List<String> path=new ArrayList<String>();
        path.add(beginWord);
        dfs(endWord,beginWord,path);
        return res;
    }

原题链接:126.单词接龙 II
参考:广度优先遍历建图 + 深度优先遍历找到所有解(Java)


程序员灯塔
转载请注明原文链接:126. 单词接龙 II
喜欢 (0)