Java的基础BFS,利用BFS实现单词接龙_单词接龙 bfs java

什么是BFS?
BFS是比较常用的搜索算法,全名为Breadth First Search(广度优先算法),相当于在考虑问题的时候,可以将所有下一步会遇到的情况考虑好,然后推演每一步直到走到想要的结果。

应用场景
1.求出到达指定目标的最小值
2.树的层序遍历

基本框架

Bfs()
{
	1. 建立起始步骤，队列初始化
	2. 遍历队列中的每一种可能，whlie(队列不为空)
	{
		通过队头元素带出下一步的所有可能，并且依次入队
		{
			判断当前情况是否达成目标：按照目标要求处理逻辑
		}
		继续遍历队列中的剩余情况
	}
}
1
2
3
4
5
6
7
8
9
10
11
12

成语接龙题目BFS实现(来源：LeetCode）
题意:
给定两个单词（beginWord 和 endWord）和一个字典，找到从 beginWord 到 endWord 的最短转换序列的长度。转换需遵循如下规则：
每次转换只能改变一个字母。
转换过程中的中间单词必须是字典中的单词。

说明 :
如果不存在这样的转换序列，返回 0。
所有单词具有相同的长度。
所有单词只由小写字母组成。
字典中不存在重复的单词。
你可以假设 beginWord 和 endWord 是非空的，且二者不相同。
如:

	输入:
	beginWord = "hit",
	endWord = "cog",
	wordList = ["hot","dot","dog","lot","log","cog"]
	输出: 5
1
2
3
4
5

BFS的基本实现最重要的组件便是队列,通过队列可以将每一步的所有情况都存入队列中,然后通过入队新情况和出队当前分析完毕的情况得到相应的结果 ,对应这道题
可以看出根据开始单词的长度n不同,每一步会有n种情况,比如:

hit ---> n = 3
*it h*t hi*   ---->对应的三种大情况    *的范围为'a'~'z'
找到里面符合字典上单词的情况,将该单词入队,成为下一步
1
2
3

也就是说我们先将hit入队,然后将所有情况分析处理,当找到了和endWord相同的情况的时候,说明已经找到了最短路径。
思路:
1.利用HashSet来存储字典单词,提高查询效率
2.为了不重复遍历,利用visited来判断一个单词是否已经用过,因为在BFS中寻找最优解,一个单词只会出现在最优先达到的那一次里,其他地方的到达路径毫无意义
3.创建队列将开始单词入队,只要队列不空就循环
4.存储队列的长度size,同时也代表着在当前步数下有多少种可能,方便记录步数
5.执行size–的内循环,循环结束意味着当初层的所有情况分析完毕,应该使result++;
6.对每一个位置进行分析,如果是endWord就return,如果不是则判断是否已经分析过该单词以及字典中是否存在,如果都满足则加入队列,成为一种考虑情况

public int ladderLength02(String beginWord, String endWord, List<String> wordList) {
        HashSet<String> wL = new HashSet<>(wordList);
        //由于需要多长判断是否包含,所以采用查询速率叫高的HashSet
        ArrayList<String> visited = new ArrayList<>();
        LinkedList<String> queue = new LinkedList<>();
        //创建队列
        int len = beginWord.length();
        int result = 1;
        queue.add(beginWord);
        while(!queue.isEmpty()){
            int size = queue.size();
            while(size-- != 0){
                String curStr = queue.poll();
                for(int i = 0 ; i < len ; i++){
                //对所有可能的情况进行处理
                    char[] newStr = curStr.toCharArray();
                    for(char j = 'a' ; j <= 'z' ; j++){
                        newStr[i] = j;
                        String t = new String(newStr);

                        if(!wL.contains(t)
                         || visited.contains(t)){
                            continue;
                        }

                        if(t.equals(endWord)){
                            return result + 1;
                        }

                        queue.add(t);
                        visited.add(t);
                    }
                }
            }
            result++;
        }
        return 0;
    }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38

按照这个思路一个基础的BFS就完成了,但此时可以看出对于查找有没有满足情况的单词会消耗大量的资源,效率较慢,一旦字典中的单词过多,或开始单词过长都容易出现很多不必要,字典中不存在的可能。
此时我们就可以在对BFS中的要求进行判断,BFS的重点就在于如何找到当前的下一步并将其成功入队,所有我们可以对字典中的值进行优化。

h*t---->hit        *ot------>hot
  \---->hot            |----->dot
1
2

事实上每一个*就代表了不同单词,而这些单词都是可以通过改变那个位置而得到的,那我们完全可以先将在同一个状态的单词放在一起,当hit寻找它的下一步时,就不需要将26个字母全部遍历完,只需要在HashMap中找到 *it这个key,所对应的ArrayList表就可以了。

思路:
1.将字典中的每个单词对应的每一个一步到达的状况全部储存,然后通过HashMap的getOrDefault()方法将老的(相同的)情况归为一组,不同的则创建新的ArrayList,完成对字典的初步处理。
2.和上面相同,创建队列进行遍历,最终找到最简的步数。

public int ladderLength3(String beginWord
, String endWord, List<String> wordList) {
        int length = beginWord.length();
        HashMap<String , ArrayList<String>> wordDir =
         new HashMap<>();

        wordList.forEach(
                word ->{

                    for(int i = 0 ; i < length ; i++){
                        char[] nStr = word.toCharArray();
                        nStr[i] = '*';
                        String newStr = new String(nStr);
                        ArrayList<String> checkList =
                                wordDir.getOrDefault(newStr,
                                 new ArrayList<>());
                        checkList.add(word);
                        wordDir.put(newStr, checkList);
                    }
                }
        );

        LinkedList<String> queue = new LinkedList<>();
        HashSet<String> visited = new HashSet<>();
        visited.add(beginWord);
        queue.add(beginWord);
        int result = 1;
        while(!queue.isEmpty()){
            int size = queue.size();
            while(size-- != 0){
                String word = queue.remove();
                for(int i = 0 ; i < length ; i++){
                    char[] nStr = word.toCharArray();
                    nStr[i] = '*';
                    String newStr = new String(nStr);
                    for(String curStr : wordDir.getOrDefault(newStr , new ArrayList<String>())){
                        if(curStr.equals(endWord)){

                            return result + 1;
                        }
                        if(!visited.contains(curStr)){
                            visited.add(curStr);
                            queue.add(curStr);
                        }
                    }
                }
            }

            result++;
        }
        return 0;
    }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52