算法-图BFS-单词接龙

阅读量：2181 次

发布时间：2019-05-01

本文共 7936 字，大约阅读时间需要 26 分钟。

算法-图BFS-单词接龙

1 题目概述

1.1 题目出处

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

1.2 题目描述

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

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

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

说明:

如果不存在这样的转换序列，返回 0。

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

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

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

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

示例 1:

输入:

beginWord = “hit”,

endWord = “cog”,

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

输出: 5

解释: 一个最短转换序列是 “hit” -> “hot” -> “dot” -> “dog” -> “cog”,

返回它的长度 5。

示例 2:

输入:

beginWord = “hit”

endWord = “cog”

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

输出: 0

解释: endWord “cog” 不在字典中，所以无法进行转换。

2 图-BFS

2.1 思路

将各单词看做无向图（因为A能转换为B，则B肯定也能转换为A），且beginWord看做图的BFS起点。只要两个单词可转变，则存在一条边。

可转变的含义是，两个单词之间有且仅有一个字符不同！

要求到达endWord的最短路径，则可从起点beginWord开始bfs，只要到达endWord肯定是最短路径！

2.2 代码

class Solution {
       public int ladderLength(String beginWord, String endWord, List
   
     wordList) {
           boolean find = false;        Map
    
     > pathMap = new HashMap<>();				// pathMap中key为单词，value为该单词能直接转换的字符串组成的list        pathMap.put(beginWord, new ArrayList
     
      ());        // 1. 首先判断字典中是否包含endWord，        // 2. 以及顺便初始化pathMap和beginWord可转变节点        for(int i = 0; i < wordList.size(); i++){
               if(endWord.equals(wordList.get(i))){
                   find = true;            }            pathMap.put(wordList.get(i), new ArrayList
      
       ());            if(connect(beginWord, wordList.get(i))){
                   pathMap.get(beginWord).add(wordList.get(i));            }        }        // 3. 如果endWord不在wordList中，则直接表示无法转变，结果返回        if(!find){
               return 0;        }        // 到这里说明endWord在wordList中，需要继续bfs判断是否beginWord->endWord        // 4. 将能直接转变的单词联通成图        for(int i = 0; i < wordList.size(); i++){
               for(int j = i + 1; j < wordList.size(); j++){
                   if(connect(wordList.get(i), wordList.get(j))){
                       pathMap.get(wordList.get(i)).add(wordList.get(j));                    pathMap.get(wordList.get(j)).add(wordList.get(i));                }            }        }                // 用于bfs的队列        LinkedList
       
         queue = new LinkedList<>();        // 已访问过的字符串        Set
        
          visited = new HashSet<>(); // 将开始字符串添加到队列头部 // 以#号分隔，左半部分是单词，右半部分是当前路径长度 queue.add(beginWord + "#" + 1); // 5.开始BFS遍历图 while(!queue.isEmpty()){ String[] oriStr = queue.poll().split("#"); String str = oriStr[0]; if(endWord.equals(str)){ // bfs时，遇到endWord时的路径肯定最短 return Integer.parseInt(oriStr[1]); } // 下一个bfs节点，路径长度+1 int nextDepth = Integer.parseInt(oriStr[1]) + 1; List
         
           connectStrList = pathMap.get(str); for(String connectStr : connectStrList){ if(!visited.contains(connectStr)){ visited.add(connectStr); queue.add(connectStr + "#" + nextDepth); } } } return 0; } // 用于判断两个字符串是否可直接转变 private boolean connect(String left, String right){ int cnt = 0; for(int i = 0; i < left.length(); i++){ if(left.charAt(i) != right.charAt(i)){ if(++cnt == 2){ return false; } } } if(cnt == 1){ return true; }else{ return false; } }}

2.3 时间复杂度

在这里插入图片描述

O(N^2 * K)

N为单词总数，K为单词长度，O(N*K)初始化 + O(N^2 * K)建立图 + O(N)遍历图

2.4 空间复杂度

最坏O(N^2 * K)

3 图-双端BFS

3.1 思路

前面BFS方法固然好，但时间太慢。可以采用双端BFS，每次从节点少（分支少）的一端遍历，加快找到连通的路径。

3.2 代码

class Solution {
       // 已访问过的字符串    private Set
   
     visited = new HashSet<>();    private Map
    
     > pathMap = new HashMap<>();    public int ladderLength(String beginWord, String endWord, List
     
       wordList) {
           boolean find = false;        pathMap.put(beginWord, new ArrayList
      
       ());        // 首先判断字典中是否包含endWord，以及顺便初始化pathMap和beginWord可转变节点        for(int i = 0; i < wordList.size(); i++){
               if(endWord.equals(wordList.get(i))){
                   find = true;            }            pathMap.put(wordList.get(i), new ArrayList
       
        ());            if(connect(beginWord, wordList.get(i))){
                   pathMap.get(beginWord).add(wordList.get(i));            }        }        if(!find){
               return 0;        }        // 将能直接转变的联通成图        for(int i = 0; i < wordList.size(); i++){
               for(int j = i + 1; j < wordList.size(); j++){
                   if(connect(wordList.get(i), wordList.get(j))){
                       pathMap.get(wordList.get(i)).add(wordList.get(j));                    pathMap.get(wordList.get(j)).add(wordList.get(i));                }            }        }        // 用于bfs        Set
        
          start = new HashSet<>(); // 将开始字符串添加到起点队列 start.add(beginWord); Set
         
           end = new HashSet<>(); // 将结束字符串添加到终点队列 end.add(endWord); // 开始BFS遍历图 return bfs(start, end, 2); } private int bfs(Set
          
            start, Set
           
             end, int depth){ if(start.size() == 0 || end.size() == 0){ return 0; } // 用来存放另一端待BFS遍历元素 HashSet
            
              next = new HashSet<>(); for(String str : start){ visited.add(str); List
             
               connectStrList = pathMap.get(str); for(String connectStr : connectStrList){ if(!visited.contains(connectStr)){ if(end.contains(connectStr)){ // bfs时，end节点包含该str时，说明可达终点，此时路径肯定最短 return depth; } next.add(connectStr); } } } // 每次从较少元素的一侧开始遍历 if(next.size() > end.size()){ return bfs(end, next, ++depth); }else{ return bfs(next, end, ++depth); } } // 用于判断两个字符串是否可直接转变 private boolean connect(String left, String right){ int cnt = 0; for(int i = 0; i < left.length(); i++){ if(left.charAt(i) != right.charAt(i)){ if(++cnt == 2){ return false; } } } if(cnt == 1){ return true; }else{ return false; } }}

3.3 时间复杂度

在这里插入图片描述

O(N^2 * K)

N为单词总数，K为单词长度，O(N*K)初始化 + O(N^2 * K)建立图 + O(N)遍历图

3.4 空间复杂度

最坏O(N^2 * K)

4 图-双端BFS-优化

4.1 思路

前面双端BFS方法固然好，但时间依然太慢。主要是前面构造pathMap花了太多时间。

我们转变下思路，不再按位挨个比较构造pathMap，而是构建一个转换Map，Key为如abc*de，value为List，值如[abcfde, abcgde, abchde]等。所以一个单词可以对应很多个这样的key, value。

在判断时，还是双端bfs，不过判断可转换节点时不再按位遍历当前字符串的每个字符，而是替换为’#'后查找同源其他字符串。

4.2 代码

class Solution {
       // 已访问过的字符串    private Set
   
     unvisited = null;    private Map
    
     > pathMap = new HashMap<>();    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;        }    }    public int ladderLength(String beginWord, String endWord, List
      
        wordList) {
           unvisited = new HashSet<>(wordList);        // 首先判断字典中是否包含endWord        if(!unvisited.contains(endWord)){
               return 0;        }				// 构建beginWord可转变节点组成的pathMap        generateRegex(beginWord);        // 构建路径节点可转变节点组成的pathMap        for(int i = 0; i < wordList.size(); i++){
               generateRegex(wordList.get(i));        }        // 用于bfs        Set
       
         start = new HashSet<>();        // 将开始字符串添加到队列头部        start.add(beginWord);        Set
        
          end = new HashSet<>(); end.add(endWord); // 开始BFS遍历图 return bfs(start, end, 2); } private int bfs(Set
         
           start, Set
          
            end, int depth){ if(start.size() == 0 || end.size() == 0){ return 0; } // 标记start集里的所有元素已访问过，避免成环重复访问 unvisited.removeAll(start); HashSet
           
             next = new HashSet<>(); for(String str : start){ char[] cs = str.toCharArray(); // 将字符串转为char[]，然后按位遍历出每一个regex对应的list for(int i = 0; i < str.length(); i++){ char tmp = cs[i]; cs[i] = '#'; String regexStr = new String(cs); // 得到该regex对应的所有StrList List
            
              connectStrList = pathMap.get(regexStr); for(String connectStr : connectStrList){ if(unvisited.contains(connectStr)){ if(end.contains(connectStr)){ // bfs时，end节点包含该str时，说明可达终点，此时路径肯定最短 return depth; } next.add(connectStr); } } cs[i] = tmp; } } if(next.size() > end.size()){ return bfs(end, next, ++depth); }else{ return bfs(next, end, ++depth); } }}