LeetCode题解——广度优先搜索(二)

青旅半醒 2023-05-30 10:50 24阅读 0赞

## 127. 单词接龙 ##

给定两个单词（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" 不在字典中，所以无法进行转换。

### BFS ###

我们将问题抽象在一个无向无权图中，每个单词作为节点，差距只有一个字母的两个单词之间连一条边。问题变成找到从起点到终点的最短路径，如果存在的话。因此可以使用广度优先搜索方法。

算法中最重要的步骤是找出相邻的节点，也就是只差一个字母的两个单词。为了快速的找到这些相邻节点，我们对给定的 wordList 做一个预处理，将单词中的某个字母用 \* 代替。

利用广度优先搜索搜索从 beginWord 到 endWord 的路径。

对给定的 wordList 做预处理，找出所有的通用状态。将通用状态记录在字典中，键是通用状态，值是所有具有通用状态的单词。

将包含 beginWord 和 1 的元组放入队列中，1 代表节点的层次。我们需要返回 endWord 的层次也就是从 beginWord 出发的最短距离。

为了防止出现环，使用访问数组记录。

当队列中有元素的时候，取出第一个元素，记为 current\_word。

找到 current\_word 的所有通用状态，并检查这些通用状态是否存在其它单词的映射，这一步通过检查 all\_combo\_dict 来实现。

从 all\_combo\_dict 获得的所有单词，都和 current\_word 共有一个通用状态，所以都和 current\_word 相连，因此将他们加入到队列中。

对于新获得的所有单词，向队列中加入元素 (word, level + 1) 其中 level 是 current\_word 的层次。

最终当你到达期望的单词，对应的层次就是最短变换序列的长度。

标准广度优先搜索的终止条件就是找到结束单词。

import javafx.util.Pair;
    class Solution {
        
        public int ladderLength(String beginWord, String endWord, List<String> wordList) {
        
            int L = beginWord.length();
            HashMap<String, ArrayList<String>> dict = new HashMap<String, ArrayList<String>>();
            wordList.forEach(
                word -> {
        
                    for(int i = 0; i < L; ++i){
        
                        String newWord = word.substring(0, i) + '*' + word.substring(i+1, L);
                        ArrayList<String> trans = dict.getOrDefault(newWord, new ArrayList<String>());
                        trans.add(word);
                        dict.put(newWord, trans);
                    }
                }
            );
            Queue<Pair<String, Integer>> Q = new LinkedList<Pair<String, Integer>>();
            Q.add(new Pair(beginWord, 1));
            HashMap<String, Boolean> visited = new HashMap<String, Boolean>();
            visited.put(beginWord, true);
            while(!Q.isEmpty()){
        
                Pair<String, Integer> node = Q.remove();
                String word = node.getKey();
                int level = node.getValue();
                for(int i = 0; i < L; ++i){
        
                    String newWord = word.substring(0, i) + '*' + word.substring(i+1, L);
                    for(String adj : dict.getOrDefault(newWord, new ArrayList<String>())){
        
                        if(adj.equals(endWord))
                            return level + 1;
                        if(!visited.containsKey(adj)){
        
                            visited.put(adj, true);
                            Q.add(new Pair(adj, level + 1));
                        }
                    }
                }
            }
            return 0;
        }
    };

### 双向广度优先搜索 ###

如果使用两个同时进行的广搜可以有效地减少搜索空间。一边从 beginWord 开始，另一边从 endWord 开始。我们每次从两边各扩展一个节点，当发现某一时刻两边都访问了某一顶点时就停止搜索。这就是双向广度优先搜索，它可以可观地减少搜索空间大小，从而降低时间和空间复杂度。

算法与之前描述的标准广搜方法相类似。

唯一的不同是我们从两个节点同时开始搜索，同时搜索的结束条件也有所变化。

我们现在有两个访问数组，分别记录从对应的起点是否已经访问了该节点。

如果我们发现一个节点被两个搜索同时访问，就结束搜索过程。因为我们找到了双向搜索的交点。过程如同从中间相遇而不是沿着搜索路径一直走。

双向搜索的结束条件是找到一个单词被两边搜索都访问过了。

最短变换序列的长度就是中间节点在两边的层次之和。因此，我们可以在访问数组中记录节点的层次。

import javafx.util.Pair;
    class Solution {
        
        private int L;
        private HashMap<String, ArrayList<String>> dict;
        Solution(){
        
            this.L = 0;
            this.dict = new HashMap<String, ArrayList<String>>();
        }
        private int visitWordNode(Queue<Pair<String, Integer>> Q, HashMap<String, Integer> visited1, HashMap<String, Integer> visited2){
        
            Pair<String, Integer> node = Q.remove();
            String word = node.getKey();
            int level = node.getValue();
            for(int i = 0; i < this.L; ++i){
        
                String newWord = word.substring(0, i) + '*' + word.substring(i + 1, L);
                for(String adj : this.dict.getOrDefault(newWord, new ArrayList<String>())){
        
                    if(visited2.containsKey(adj)){
        
                        return level + visited2.get(adj);
                    }
                    if(!visited1.containsKey(adj)){
        
                        visited1.put(adj, level + 1);
                        Q.add(new Pair(adj, level + 1));
                    }
                }
            }
            return -1;
        }
        public int ladderLength(String beginWord, String endWord, List<String> wordList) {
        
            if(!wordList.contains(endWord)){
        
                return 0;
            }
            this.L = beginWord.length();
            wordList.forEach(
                word -> {
        
                    for(int i = 0; i < L; i++){
        
                        String newWord = word.substring(0, i) + '*' + word.substring(i+1, L);
                        ArrayList<String> trans = this.dict.getOrDefault(newWord, new ArrayList<String>());
                        trans.add(word);
                        this.dict.put(newWord, trans);
                    }
                }
            );
            Queue<Pair<String, Integer>> qbegin = new LinkedList<Pair<String, Integer>>();
            Queue<Pair<String, Integer>> qend = new LinkedList<Pair<String, Integer>>();
            qbegin.add(new Pair(beginWord, 1));
            qend.add(new Pair(endWord, 1));
            HashMap<String, Integer> visited1 = new HashMap<String, Integer>();
            HashMap<String, Integer> visited2 = new HashMap<String, Integer>();
            visited1.put(beginWord, 1);
            visited2.put(endWord, 1);
            while(!qbegin.isEmpty() && !qend.isEmpty()){
        
                int ans = visitWordNode(qbegin, visited1, visited2);
                if(ans > -1){
        
                    return ans;
                }
                ans = visitWordNode(qend, visited2, visited1);
                if(ans > -1){
        
                    return ans;
                }
            }
            return 0;
        }
    };