首页 > 代码库 > [C++]LeetCode: 130 Word Ladder (BFS)

[C++]LeetCode: 130 Word Ladder (BFS)

2024-11-21 00:09:41   202人阅读

题目：

Given two words (start and end), and a dictionary, find the length of shortest transformation sequence from start to end, such that:

  1. Only one letter can be changed at a time
  2. Each intermediate word must exist in the dictionary

For example,

Given:
start = "hit"
end = "cog"
dict = ["hot","dot","dog","lot","log"]

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.
思路：可以将这道题看成是一个图的问题。我们将题目映射到图中，顶点是每个字符串，然后两个字符串如果相差一个字符则进行连边。我们的字符集只有小写字母，而且字符串的长度固定，假设是L。那么可以注意到每一个字符可以对应的边有25个（26个小写字母去掉自己），那么一个字符串可能存在的边是25*L条。接下来就是检查这些对应的字符串是否在字典内，就可以得到一个完整的图的结构。根据题目要求，等价于求这个图中一个顶点到另一个顶点的最短路径，我们一般用广度优先。
这道题，我们只能用最简单的办法去做，每次改变单词的一个字母，然后逐渐搜索，这种求最短路径，树最小深度问题用BFS最合适。注意一下几点
  • 和当前单词相邻的单词，就是和顶点共边的另一个顶点，是对当前单词改变一个字母且在字典内存在的单词
  • 找到一个单词的相邻单词，加入BFS队列后，我们要从字典内删除，因为不删除会造成类似hog->hot->hog这样的死循环。而且删除对求最短路径没有影响，因为我们第一次找到的单词肯定是最短路径，我们是层序遍历去搜索的，最早找到的一定是最短路径，即使后面的其他单词也能转换成它，路径肯定不会比当前的路径短。这道题仅要求求出最短路径长度，不需要求输出最短路径，所以可以删除这个单词。
  • BFS队列之间用空串“”来标示层与层的间隔，每次碰到层的结尾，遍历深度+1，进入下一层。
Attention:
1. 根据题目设定，路径长度包含开头和结尾。所以刚开始初始化path为1.
int path = 1;
2. 我们使用空串“”来作为层与层的分隔符，不同于树的结点，我们用NULL。这里字符串和NULL无法进行比较。
 if(str != NULL)
Line 16: no match for ‘operator!=’ (operand types are ‘std::string {aka std::basic_string<char>}’ and ‘long int’)
3. 我们在改变一个单词的每一个字母时，需要首先保存这个字符，然后再去搜索匹配。最后全部搜索完，还需要恢复现场。
char tmp = str[i];
str[i] = tmp;  //重置回原来的单词
4. set 删除元素
(1)
iterator  erase (const_iterator position);
(2)
size_type erase (const value_type& val);
(3)
iterator  erase (const_iterator first, const_iterator last);
5. 如果当前的字符串在改变一个字母后，得到end，说明转换结束。返回path+1. end和start不需要在字典内。这是BFS搜索的终止条件。
if(str == end) return path + 1; //如果改变后的单词等于end 返回path+1
复杂度：最坏情况就是把所有长度为L的字符串都看一遍，或者字典内的字符串都看一遍。长度为L的字符串总共有26^L.时间复杂度O(26^L)，空间上需要存储访问情况，O(size(dict)).
AC Code:
class Solution {
public:
    int ladderLength(string start, string end, unordered_set<string> &dict) {
        if(start.size() == 0 || end.size() == 0) return 0;
        
        queue<string> wordQ;
        wordQ.push(start);
        wordQ.push("");
        int path = 1;
        
        while(!wordQ.empty())
        {
            string str = wordQ.front();
            wordQ.pop();
            
            if(str != "")
            {
                int len = str.size();
                for(int i = 0; i < len; i++)
                {
                    char tmp = str[i];
                    
                    for(char c = 'a'; c <= 'z'; c++)
                    {
                        if(c == tmp) continue;
                        str[i] = c;
                        if(str == end) return path + 1; //如果改变后的单词等于end 返回path+1
                        if(dict.find(str) != dict.end())
                        {
                            wordQ.push(str);
                            dict.erase(str);   //字典内删除这个词 防止反复走
                        }
                    }
                    str[i] = tmp;  //重置回原来的单词
                }
            }
            else if(!wordQ.empty())
            {
                //到达当前层的结尾，并且不是最后一层的结尾
                path++;
                wordQ.push("");
            }
        }
        return 0;
    }
};

这道题的本质框架就是广度优先搜索，只不过判断边的时候需要换字符和查字典的操作，这属于图的搜索的基础算法。Clone Graph.






[C++]LeetCode: 130 Word Ladder (BFS)


联系
我们