leetcode 127. Word Ladder BFS广度优先遍历

悠悠 2022-06-08 05:35 164阅读 0赞

Given two words (beginWord and endWord), and a dictionary’s word list, find the length of shortest transformation sequence from beginWord to endWord, such that:

Only one letter can be changed at a time.  
Each transformed word must exist in the word list. Note that beginWord is not a transformed word.  
For example,

Given:  
beginWord = “hit”  
endWord = “cog”  
wordList = \[“hot”,”dot”,”dog”,”lot”,”log”,”cog”\]  
As one shortest transformation is “hit” -> “hot” -> “dot” -> “dog” -> “cog”,  
return its length 5.

Note:  
Return 0 if there is no such transformation sequence.  
All words have the same length.  
All words contain only lowercase alphabetic characters.  
You may assume no duplicates in the word list.  
You may assume beginWord and endWord are non-empty and are not the same.  
UPDATE (2017/1/20):  
The wordList parameter had been changed to a list of strings (instead of a set of strings). Please reload the code definition to get the latest changes.

这道题考察的就是最短的改动次数，使用BFS广度优先遍历即可完成，我也是在网上看了一个博主的教程完成的，做法很棒，一看即懂，很值得学习。

建议和这一道题[leetcode 433. Minimum Genetic Mutation 和Word Ladder一样BFS + 反向链表 + DFS][leetcode 433. Minimum Genetic Mutation _Word Ladder_BFS _ _ _ DFS] 和 [leetcode 126. Word Ladder II BFS + 反向链表 + DFS][leetcode 126. Word Ladder II BFS _ _ _ DFS] 一起学习

还有[leetcode 752. Open the Lock 开锁 + 十分典型的广度优先遍历BFS][leetcode 752. Open the Lock _ _ _BFS]

**注意这道题很值得学习BFS。**

代码如下：

import java.util.HashMap;
    import java.util.HashSet;
    import java.util.LinkedList;
    import java.util.List;
    import java.util.Map;
    import java.util.Queue;
    import java.util.Set;
    public class Solution
    {
        /*
         * 我也是看了博主的BFS做法，顿时茅塞大开，的确很不错的做法 
         * http://blog.csdn.net/zdavb/article/details/48135823
         * */
        public int ladderLength(String beginWord, String endWord, List<String> wordList) 
        {
            Set<String> wordSet = new HashSet<>(wordList);
            Queue<String> queue = new LinkedList<String>();
            if(wordSet.contains(beginWord))
                wordSet.remove(beginWord);
            queue.add(beginWord);
    
            // 这个是使用map来记录word和level（树的深度）的对应关系 
            Map<String, Integer> map = new HashMap<String, Integer>();
            map.put(beginWord, 1);
            //wordSet.size()!=0 是处理 无法完成transform的情况
            while(queue.isEmpty()==false && wordSet.size()!=0)
            {
                //当前的元素出队列，curNum--
                String word = queue.poll();
                int level = map.get(word);
                //下面两个循环分别是替换一个元素的暴力查找
                for(int i=0;i<word.length();i++)
                {
                    char[] array = word.toCharArray();
                    for(char j='a';j<='z';j++)
                    {
                        array[i]=j;
                        String tmp = new String(array);
                        //假如找到了下一个元素，直接返回，因为是最短路径，
                        //所以最先找到的就是最短的
                        if(wordSet.contains(tmp))
                        {
                            if(tmp.equals(endWord))
                                return level+1;
                            else
                            {
                                queue.add(tmp);
                                wordSet.remove(tmp);
                                map.put(tmp, level+1);
                            }
                        }   
                    }
                }
            }   
            return 0;
        }
    
    
        /*
         * http://blog.csdn.net/mine_song/article/details/68951974
         * */
        public int ladderLengthByBFS(String beginWord, String endWord, List<String> wordList) 
        {
            Set<String> wordSet = new HashSet<>(wordList);
            Queue<String> queue = new LinkedList<String>();
            if(wordSet.contains(beginWord))
                wordSet.remove(beginWord);
            queue.add(beginWord);
    
            int currNum=1;//当前level的结点数量
            int nextNum=0;//下一个level的结点数量
            int level=1;//level计数
    
            while(queue.isEmpty()==false)
            {
                //当前的元素出队列，curNum--
                String word = queue.poll();
                currNum--;
                //下面两个循环分别是替换一个元素的暴力查找
                for(int i=0;i<word.length();i++)
                {
                    char[] array = word.toCharArray();
                    for(char j='a';j<='z';j++)
                    {
                        array[i]=j;
                        String tmp = new String(array);
                        //假如找到了下一个元素，直接返回，因为是最短路径，
                        //所以最先找到的就是最短的
                        if(wordSet.contains(tmp))
                        {
                            if(tmp.equals(endWord))
                                return level+1;
                            else
                            {
                                queue.add(tmp);
                                nextNum++;
                                wordSet.remove(tmp);
                            }
                        }   
                    }
                }
                //当前level遍历完成，回到下一层
                if(currNum==0)
                {
                    currNum = nextNum;
                    nextNum =0;
                    level++;
                }
            }
            return 0;
        }
    }

下面是C++的做法，就是做一个BFS广度优先遍历，**这道真题很值得学习和掌握**

代码如下：

#include <iostream>
    #include <vector>
    #include <algorithm>
    #include <climits>
    #include <set>
    #include <map>
    #include <queue>
    
    using namespace std;
    
    class Solution 
    {
    public:
        int ladderLength(string beginWord, string endWord, vector<string>& wordList) 
        {
            set<string> wordSet(wordList.begin(),wordList.end());
            if (wordSet.find(beginWord) != wordSet.end())
                wordSet.erase(beginWord);
    
            queue<string> que;
            map<string, int> mp;
            int level = 1;
            que.push(beginWord);
            mp[beginWord] = level;
            while (que.empty()==false)
            {
                string now = que.front();
                que.pop();
                int level = mp[now];
                for (int i = 0; i < now.length(); i++)
                {
                    string tmp = now;
                    for (char j = 'a'; j <= 'z'; j++)
                    {
                        tmp[i] = j;
                        if (wordSet.find(tmp) != wordSet.end())
                        {
                            if (tmp == endWord)
                                return level + 1;
                            else
                            {
                                que.push(tmp);
                                wordSet.erase(tmp);
                                mp[tmp] = level + 1;
                            }
    
                        }
                    }
                }
            }
            return 0;
        }
    };

[leetcode 433. Minimum Genetic Mutation _Word Ladder_BFS _ _ _ DFS]: http://blog.csdn.net/JackZhang_123/article/details/78773078
[leetcode 126. Word Ladder II BFS _ _ _ DFS]: http://blog.csdn.net/jackzhang_123/article/details/78002641
[leetcode 752. Open the Lock _ _ _BFS]: http://blog.csdn.net/JackZhang_123/article/details/78899781