算法-图BFS-单词接龙

我不是女神ヾ 2023-03-13 11:42 5阅读 0赞

# 算法-图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<String> wordList) { 
            boolean find = false;
            Map<String, List<String>> pathMap = new HashMap<>();
    		
    		// pathMap中key为单词，value为该单词能直接转换的字符串组成的list
            pathMap.put(beginWord, new ArrayList<String>());
    
            // 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<String>());
                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<String> queue = new LinkedList<>();
            // 已访问过的字符串
            Set<String> 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<String> 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 时间复杂度 ##

![在这里插入图片描述][20200513110805971.png]  
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<String> visited = new HashSet<>();
        private Map<String, List<String>> pathMap = new HashMap<>();
        public int ladderLength(String beginWord, String endWord, List<String> wordList) { 
            boolean find = false;
    
            pathMap.put(beginWord, new ArrayList<String>());
    
            // 首先判断字典中是否包含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<String>());
                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<String> start = new HashSet<>();
            // 将开始字符串添加到起点队列
            start.add(beginWord);
    
            Set<String> end = new HashSet<>();
            // 将结束字符串添加到终点队列
            end.add(endWord);
    
            // 开始BFS遍历图
            return bfs(start, end, 2);
        }
        private int bfs(Set<String> start, Set<String> end, int depth){ 
            if(start.size() == 0 || end.size() == 0){ 
                return 0;
            }
            // 用来存放另一端待BFS遍历元素
            HashSet<String> next = new HashSet<>();
            for(String str : start){ 
                visited.add(str);
                List<String> 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 时间复杂度 ##

![在这里插入图片描述][20200513131830654.png]  
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<String> unvisited = null;
        private Map<String, List<String>> 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<String> 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<String> 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<String> start = new HashSet<>();
            // 将开始字符串添加到队列头部
            start.add(beginWord);
    
            Set<String> end = new HashSet<>();
            end.add(endWord);
    
            // 开始BFS遍历图
            return bfs(start, end, 2);
        }
        private int bfs(Set<String> start, Set<String> end, int depth){ 
            if(start.size() == 0 || end.size() == 0){ 
                return 0;
            }
            // 标记start集里的所有元素已访问过，避免成环重复访问
            unvisited.removeAll(start);
            HashSet<String> 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<String> 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);
            }
        }
    }

## 4.3 时间复杂度 ##

*  O(N \* K)  
    N为单词总数，K为单词长度，`O(N * K)`构建pathMap + `O(N * K )`查找  
    ![在这里插入图片描述][2020051314594174.png]  
    这次优化很大！

## 4.4 空间复杂度 ##

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

[20200513110805971.png]: /images/20230312/d238e8c2d65d4e73b277319397626ebf.png
[20200513131830654.png]: /images/20230312/db57604c99d5499b83c356702cae67a1.png
[2020051314594174.png]: https://img-blog.csdnimg.cn/2020051314594174.png