[数据结构与算法]leetcode 127. 单词接龙—(每日一难day6)

127. 单词接龙

字典 wordList 中从单词 beginWord 和 endWord 的 转换序列 是一个按下述规格形成的序列 beginWord -> s1 -> s2 -> … -> sk：

• 每一对相邻的单词只差一个字母。
• 对于 1 <= i <= k 时，每个 si 都在 wordList 中。注意， beginWord
  不需要在 wordList 中。
• sk == endWord

给你两个单词 beginWord 和 endWord 和一个字典 wordList ，返回 从 beginWord 到 endWord 的 最短转换序列 中的 单词数目 。如果不存在这样的转换序列，返回 0 。

示例 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” 不在字典中，所以无法进行转换。

提示：

1. 1 <= beginWord.length <= 10
2. endWord.length == beginWord.length
3. 1<=wordList.length <= 5000
4. wordList[i].length == beginWord.length
5. beginWord、endWord 和 wordList[i] 由小写英文字母组成 beginWord != endWord
6. wordList 中的所有字符串 互不相同

解析

1. 怎么想起来建图呢？由于单词的转移方式时固定的，只能往相似的单词转移
2. 然后从开始处层次遍历，每次需要记住层次遍历所对应的层次，遇到end就返回
3. 优化：也可以从结束点，起始点同时遍历，如果在到达起始点之前遇到相同的单词，说明可以到达，将两者到达该单词的距离相加即可。再次过程中可以将两者访问过的单词放入同一个map。

code

class Solution {
public:
    bool is_similar(string s1,string s2){
        int cnt=0;
        if(s1.size()!=s2.size())
            return false;
        int n=s1.size();
        int i=0;
        while(i<n){
            if(s1[i]!=s2[i])
                cnt++;
            i++;
        }
        // 如果相差一个字母，就返回true；
        return cnt==1;
    }
    int ladderLength(string beginWord, string endWord, vector<string>& wordList) {
        wordList.push_back(beginWord);
        int n=wordList.size();
        //创建相似图
        unordered_map<string,vector<string>> g;
        // 无向邻接矩阵
        for(int i=0;i<n;i++){
            for(int j=i+1;j<n;j++){
                if(is_similar(wordList[i],wordList[j])){
                    g[wordList[i]].push_back(wordList[j]);
                    g[wordList[j]].push_back(wordList[i]);
                }    
            }
        }
        queue<pair<string,int>> q;
        q.push(make_pair(beginWord,1));
        unordered_set<string> visited;
        visited.insert(beginWord);
        int res=0;
        while(!q.empty()){
            string s=q.front().first;
            int tmp=q.front().second;
            q.pop();
            for(auto s1:g[s]){
                if(visited.find(s1)!=visited.end())
                    continue;
                if(s1==endWord)
                    return tmp+1;
                visited.insert(s1);
                q.push(make_pair(s1,tmp+1));
            }
        }
        return 0;
    }
};

创作打卡挑战赛

赢取流量/现金/CSDN周边激励大奖