题目分析

这个题目在前几天讲解过，是Leetcode126和Leetcode127题的姐妹题，当时讲解的是第127题求最短的转换序列长度，当时的最优算法是BFS，原因也经常叙述了，找到最近的一条就是BFS，找到任意一条就是DFS，在这里是求任意一条，因此最优解也非常明显，小伙伴们先尝试去做。

DFS

当列表单词很多的时候，我们可以枚举单词的位置，枚举每个位置的字符，假如有字典中10000个单词，每个单词长度为10。如果我们逐一和所有单词比较是否相差一个字符，就需要10000次比较，如果只是枚举长度和可能出现的单词，只需要枚举10*26=260次。这个技巧在处理字符串问题时非常重要，希望小伙伴们务必掌握它。

我们对单词列表进行深搜，当搜索到了则返回true，否则将该点加入visited并且返回false。加入visited的目的是剪枝，防止通过其他的路径再次到达该点进行搜索。

算法的时间复杂度为$O(mn)$，空间复杂度为$O(mn)$，其中n为字典中单词的个数，m为每个单词的长度。

#include<iostream>
#include<vector>
#include<set>

using namespace std;

class Solution {
public:
    vector<string> findLadders(string beginWord, string endWord, vector<string>& wordList) {
        vector<string> cur = { beginWord };
        set<string> path = {beginWord}, newWords, visited;
        for (string s : wordList) if (s.size() == beginWord.size()) newWords.insert(s);
        if (dfs(cur, path, newWords, endWord, visited)) return cur;
        return vector<string>();
    }

    bool dfs(vector<string>& cur, set<string>& path, set<string>& newWords, string endWord, set<string>& visited) {
        if (cur.back() == endWord) {
            return true;
        }
        if (visited.count(cur.back())) return false;
        for (int i = 0; i < cur[0].size(); i++) {
            string curString = cur.back();
            for (int j = 0; j < 26; j++) {
                curString[i] = 'a' + j;
                if (newWords.count(curString) && !path.count(curString)) {
                    cur.push_back(curString);
                    path.insert(curString);
                    if (dfs(cur, path, newWords, endWord, visited)) return true;
                    visited.insert(curString);
                    cur.pop_back();
                    path.erase(curString);
                }
            }
        }
        return false;
    }
};

BFS

我们对单词列表进行广搜，当搜索到了直接return即可，否则将该点加入visited并且继续搜索。加入visited的目的也是剪枝，防止通过其他的路径再次到达该点进行搜索。

我在这个算法中每一次搜索都保存了所有的路径，因此空间复杂度为$O(mn^2)$。

可以使用哈希表记录最先到达某点的路径，这样可以追溯求出路径，这样只适合于求最短路径，并不是这类问题的通解。如果要求出所有路径，就无法做到了。所有有兴趣的小伙伴可以尝试去做。

算法的时间复杂度为$O(mn^2)$，空间复杂度为$O(mn)$，其中n为字典中单词的个数，m为每个单词的长度。

#include<iostream>
#include<vector>
#include<deque>
#include<set>

using namespace std;

class Solution {
public:
    vector<string> findLadders(string beginWord, string endWord, vector<string>& wordList) {
        deque<vector<string>> queue = { { beginWord } };
        set<string> visited = { beginWord }, newWords;
        for (string s : wordList) if (s.size() == beginWord.size()) newWords.insert(s);
        while (!queue.empty()) {
            vector<string> cur = queue.front();
            queue.pop_front();
            for (int i = 0; i < cur[0].size(); i++) {
                string curString = cur.back();
                for (int j = 0; j < 26; j++) {
                    curString[i] = 'a' + j;
                    if (newWords.count(curString) && !visited.count(curString)) {
                        cur.push_back(curString);
                        visited.insert(curString);
                        if (curString == endWord) return cur;
                        queue.push_back(cur);
                        cur.pop_back();
                    }
                }
            }
        }
        return vector<string>();
    }
};

单词转换(Leetcode 程序员面试金典17.22)

题目分析

DFS

BFS

刷题总结