leetcode127.单词接龙

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

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

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

示例：

1
2
3

输入：beginWord = "hit", endWord = "cog", wordList = ["hot","dot","dog","lot","log","cog"]
输出：5
解释：一个最短转换序列是 "hit" -> "hot" -> "dot" -> "dog" -> "cog", 返回它的长度 5。

分析：

1	由于题目要求没对相邻单词之间仅有单个字母不同，即从当前状态到下一个状态代价为1，同时题目要求最短转化路近，因此问题转化为BFS求最短路问题

代码

逆向搜索

class Solution {
public:
    int len, min_dis;
    unordered_set<string> seen;
    unordered_map<string, int> d;
    string ed;

    void bfs() {
        queue<string> q;
        q.push(ed);
        d[ed] = 1;

        while (!q.empty()) {
            auto u = q.front();
            q.pop();
            for (int i = 0;i < len;i ++) {
                string v = u;
                for (char ch = 'a';ch <= 'z';ch ++) {
                    v[i] = ch;
                    if (seen.find(v) == seen.end()) continue;
                    if (d.find(v) == d.end()) d[v] = d[u] + 1, q.push(v);
                    
                }
            }
        }
    }

    int ladderLength(string beginWord, string endWord, vector<string>& wordList) {
        len = beginWord.size();
        seen = unordered_set<string>(wordList.begin(), wordList.end());
        if (seen.find(endWord) == seen.end()) return 0;
        seen.insert(beginWord);
        ed = endWord;
        bfs();

        return d[beginWord];
    }
};

正向搜索

class Solution {
public:
    int len, min_dis;
    unordered_set<string> seen;
    unordered_map<string, int> d;
    string ed;
    int bfs(const string& s) {
        queue<string> q;
        q.push(s);
        d[s] = 1;

        while (!q.empty()) {
            auto u = q.front();
            q.pop();
            for (int i = 0;i < len;i ++) {
                string v = u;
                for (char ch = 'a';ch <= 'z';ch ++) {
                    v[i] = ch;
                    if (seen.find(v) == seen.end()) continue;
                    if (d.find(v) == d.end()) d[v] = d[u] + 1, q.push(v);
                    if (v == ed) return d[v];
                    
                }
            }
        }

        return 0;
    }

    int ladderLength(string beginWord, string endWord, vector<string>& wordList) {
        len = beginWord.size();
        seen = unordered_set<string>(wordList.begin(), wordList.end());
        if (seen.find(endWord) == seen.end()) return 0;
        seen.insert(beginWord);
        ed = endWord;
        return bfs(beginWord);
    }
};

[原题链接](127. 单词接龙 - 力扣（Leetcode）)

[相似题目](126. 单词接龙 II - 力扣（Leetcode）)

代码

C++

逆向搜索

正向搜索