算法-图BFS-单词接龙2

1 题目概述

1.1 题目出处

https://leetcode-cn.com/problems/word-ladder-ii/

1.2 题目描述

给定两个单词（beginWord 和 endWord）和一个字典 wordList，找出所有从 beginWord 到 endWord 的最短转换序列。转换需遵循如下规则：

每次转换只能改变一个字母。

转换过程中的中间单词必须是字典中的单词。

说明:

如果不存在这样的转换序列，返回一个空列表。

所有单词具有相同的长度。

所有单词只由小写字母组成。

字典中不存在重复的单词。

你可以假设 beginWord 和 endWord 是非空的，且二者不相同。

示例 1:

输入:

beginWord = “hit”,

endWord = “cog”,

wordList = [“hot”,“dot”,“dog”,“lot”,“log”,“cog”]

输出:

[

[“hit”,“hot”,“dot”,“dog”,“cog”],

[“hit”,“hot”,“lot”,“log”,“cog”]

]

示例 2:

输入:

beginWord = “hit”

endWord = “cog”

wordList = [“hot”,“dot”,“dog”,“lot”,“log”]

输出: []

解释: endWord “cog” 不在字典中，所以不存在符合要求的转换序列。

2 图-BFS

2.1 思路

构建一个转换Map，Key为如abc*de，value为List，值如[abcfde, abcgde, abchde]等。所以一个单词可以对应很多个这样的key, value。

在判断可转换节点时，按位遍历当前字符串的每个字符，替换为’#'后查找同源其他字符串。

2.2 代码

class Solution {
       // 未访问过的字符串    private Set
   
     unvisited = null;    private Map
    
     > pathMap = new HashMap<>();    private List
     
      
       > resultList = new ArrayList<>();    // 记录某个字符串被前面若干字符串引用构成的若干list    private Map
       
        >> preListMap = new HashMap<>();    public List
        
         
          > findLadders(String beginWord, String endWord, List
          
            wordList) { unvisited = new HashSet<>(wordList); if(!unvisited.contains(endWord)){ return resultList; } unvisited.add(beginWord); generateRegex(beginWord); // 首先判断字典中是否包含endWord，以及顺便初始化pathMap和beginWord可转变节点 for(String str : unvisited){ generateRegex(str); } // 用于bfs Set
           
             start = new HashSet<>(); // 将开始字符串添加到队列头部 start.add(beginWord); Set
            
              end = new HashSet<>(); end.add(endWord); // 开始BFS遍历图 bfs(start, end, 2); // 最后返回填充好的结果列表 return resultList; } private void generateRegex(String str){ char[] cs = str.toCharArray(); for(int j = 0; j < cs.length; j++){ char tmp = cs[j]; cs[j] = '#'; String regexStr = new String(cs); List
             
               strList = pathMap.get(regexStr); if(strList == null){ strList = new ArrayList<>(); pathMap.put(regexStr, strList); } strList.add(str); cs[j] = tmp; } } private void bfs(Set
              
                start, Set
               
                 end, int depth){ if(start.size() == 0 || end.size() == 0){ return; } // 标记start集里的所有元素已访问过，避免成环重复访问 unvisited.removeAll(start); HashSet
                
                  next = new HashSet<>(); // 表示这一轮bfs是否找到一个最短路径 String targetStr = null; for(String str : start){ List
                 
                  
                   > startLists = preListMap.get(str); if(null == startLists){ startLists = new ArrayList<>(); List
                   
                     startList = new ArrayList<>(); startLists.add(startList); startList.add(str); preListMap.put(str, startLists); } char[] cs = str.toCharArray(); for(int i = 0; i < str.length(); i++){ char tmp = cs[i]; cs[i] = '#'; String regexStr = new String(cs); List
                    
                      connectStrList = pathMap.get(regexStr); for(String connectStr : connectStrList){ if(unvisited.contains(connectStr)){ // 该字符串所在若干路径列表 List
                     
                      
                       > newLists = preListMap.get(connectStr); if(null == newLists) { // 为空时，说明还没有被其他路径作为next预处理 // 此时初始化一个newLists用来存放路径 newLists = new ArrayList(); preListMap.put(connectStr, newLists); } // 不为空时，说明已经被其他路径作为next预处理过 // 将当前遍历节点的路径startLists添加到该connectStr的路径中 // 这里注意一定要用克隆的方式，不然会影响其他connectStr for(List
                       
                         startList : startLists){ List
                        
                          newList = new ArrayList(startList); newList.add(connectStr); newLists.add(newList); } if(end.contains(connectStr)){ // bfs时，end节点包含该str时，说明可达重点，此时路径肯定最短 targetStr = connectStr; }else{ next.add(connectStr); } } } cs[i] = tmp; } } if(null != targetStr){ // 此轮bfs找到了最短路径，就不再往下层搜索其他路径了 // 此时将包含终点的全部路径放入resultList，不再继续搜索 List
                         
                          
                           > newLists = preListMap.get(targetStr); for(List
                           
                             newList : newLists){ resultList.add(new ArrayList(newList)); } return; } bfs(next, end, ++depth); }}

2.3 时间复杂度

O(N * K)
N为单词总数，K为单词长度，O(N * K)构建pathMap + O(N * K )查找

2.4 空间复杂度

最坏O(N * K * 26) => O(N * K)

转载地址：http://cmpkb.baihongyu.com/

你可能感兴趣的文章