欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页  >  IT编程

数据结构算法--单词接龙(C++)

程序员文章站 2022-04-15 23:39:03
127. 单词接龙 - 力扣(LeetCode)要找最短的,直接bfs,bfs找到的肯定是最短的。抽象在一个无向无权图中,每个单词作为节点,差距只有一个字母的两个单词之间连一条边。问题变成找到从起点到终点的最短路径,如果存在的话。因此可以使用广度优先搜索方法。相当于每条边权值均为1的有向图,如果起始单词改变一个字母可以变为另一个单词,那么这两个单词之间的距离为1,否则为无穷。怎么确定一个单词改变一个字母是不是能成为另一个单词呢?可以遍历两个单词进行统计,但是如果单词表太大的话,速度会很慢。由于只...

要找最短的,直接bfs,bfs找到的肯定是最短的。

抽象在一个无向无权图中,每个单词作为节点,差距只有一个字母的两个单词之间连一条边。问题变成找到从起点到终点的最短路径,如果存在的话。因此可以使用广度优先搜索方法。
数据结构算法--单词接龙(C++)

相当于每条边权值均为1的有向图,如果起始单词改变一个字母可以变为另一个单词,那么这两个单词之间的距离为1,否则为无穷。

怎么确定一个单词改变一个字母是不是能成为另一个单词呢?可以遍历两个单词进行统计,但是如果单词表太大的话,速度会很慢。

由于只有小写字母,可以使用遍历字母的方法,一次性检查所有的单词,具体减代码;

class Solution {
public:
    int ladderLength(string beginWord, string endWord, vector<string>& wordList) {
        unordered_set<string>  s(wordList.begin(), wordList.end());

        queue<pair<string, int>> q;
        q.push({beginWord, 1});//第一个元素是字符串,第二个是该字符串到beginword的序列长度

        while(!q.empty()){
            string tmp = q.front().first;
            int step = q.front().second;
            q.pop();
            if(tmp == endWord)  return step;//走到了终点

            for(int i = 0; i < tmp.size(); ++i){
                char ch = tmp[i];
                //遍历字母来寻找距离为1(只用改变一个字母)的单词
                for(char c = 'a'; c <= 'z'; ++c){
                    if(ch == c) continue;
                    tmp[i] = c;//替换单个字符
                    if(s.count(tmp)){
                        q.push({tmp, 1+step});
                        s.erase(tmp);//该节点使用过了,可以删除
                    }
                }
                tmp[i] = ch;//复原
            }
        }
        return 0;
    }
}; 

其中查找的部分,其实还可以使用字典树实现。

本文地址:https://blog.csdn.net/qq_32523711/article/details/108239342