【力扣】面试题17.22.单词转换

题目描述

• 原题链接

思路分析

dfs

• 题目要求要到一条路径从beginWord到endWord，且路径单词需在wordList中
• 经典DFS题目，即枚举下一个可能的单词，直到找到正确答案即返回
• 用unordered_set来记录遍历过的单词
  • 防止重复遍历
  • 只需要加入，不需要弹出，因为一旦有某个单词无法继续推进，后续用到此单词的情况也不可能继续推进

class Solution {
private:
    vector<string> res;

    bool check(string& s, string& word) {
        int cnt = 0;
        for (int i = 0; i < s.size(); i++) {
            if (s[i] != word[i]) cnt++;
        }

        return cnt == 1;
    }

    bool dfs(string& beginWord, string& endWord, vector<string>& wordList, unordered_set<string>& visited) {
        res.push_back(beginWord);
        visited.insert(beginWord);
        if (beginWord == endWord) {
            return true;
        }
        // 从beginword出发，枚举后面可能的情况
        for (auto& s : wordList) {
            if (visited.count(s)) continue;
            // 查找哪一个是和我们当前的begunword只有一字之差
            if (check(s, beginWord)) {
                if (dfs(s, endWord, wordList, visited)) {
                    return true;
                }
            }
        }
        res.pop_back();
        return false;
    }

public:
    vector<string> findLadders(string beginWord, string endWord, vector<string>& wordList) {
        unordered_set<string> visited;
        dfs(beginWord, endWord, wordList, visited);

        return res;
    }
};

参考