力扣-面试题 17.22题 单词转换（C++）- dfs+回溯

题目链接：https://leetcode.cn/problems/word-transformer-lcci/
题目如下：

class Solution {
public:
    vector findLadders(string beginWord, string endWord, vector& wordList) {
        vector res;
        unordered_set uset;
        for(auto e:wordList){
            uset.insert(e);
        }
        uset.erase(beginWord);//从集合中去除掉首个string，并依次往下遍历
        if(uset.count(endWord)!=0){
            res.push_back(beginWord);
            if(dfs(beginWord,endWord,uset,res)) return res;
        }
        
        return {};
    }
    bool dfs(string& beginWord,string& endWord,unordered_set& uset,vector& res){
        if(beginWord==endWord) return true;

        for(int i=0;i
            char temp=beginWord[i];
            for(char c='a';c<='z';c++){
                beginWord[i]=c;
                if(uset.count(beginWord)!=0){
                    uset.erase(beginWord);
                    //回溯，把满足条件的放入vector，否则回溯
                    res.push_back(beginWord);
                    if(dfs(beginWord,endWord,uset,res)) return true;
                    res.pop_back();
                }
            }
            beginWord[i]=temp;
        }

        return false;
    }
};