leetcode ----数组系列--面试题 17.22. 单词转换 DFS（C++）

面试题 17.22. 单词转换 DFS（C++）

题目描述：

给定字典中的两个词，长度相等。写一个方法，把一个词转换成另一个词， 但是一次只能改变一个字符。每一步得到的新词都必须能在字典中找到。

编写一个程序，返回一个可能的转换序列。如有多个可能的转换序列，你可以返回任何一个。

示例 1:

示例 2:

输入:
beginWord = “hit”
endWord = “cog”
wordList = [“hot”,“dot”,“dog”,“lot”,“log”]
输出: []
解释: endWord “cog” 不在字典中，所以不存在符合要求的转换序列。

DFS遍历，每访问一个字符串，就对其进行标记。

vector<bool> visited;

    bool check_word(string word1, string word2)//word1 和 word2 是否只有一位不同
    {
        int n1 = word1.size(), n2 = word2.size(), cnt = 0;
        if(n1 != n2) return false;
        for(int i=0;i<n1;i++)
        {
            if(word1[i] != word2[i]) cnt++;
        }
        return cnt == 1;
    }

    bool dfs(string beginWord, string endWord, vector<string>& wordList, vector<string>& path)
    {
        if(beginWord == endWord) return true;
        int n = wordList.size();
        for(int i=0;i<n;i++)
        {
            if(visited[i] == true || check_word(beginWord, wordList[i]) == false)
                continue;
            visited[i] = true;
            path.push_back(wordList[i]);
            if(dfs(wordList[i], endWord, wordList, path) == true)
                return true;
            path.pop_back();
        }
        return false;
    }

    vector<string> findLadders(string beginWord, string endWord, vector<string>& wordList)
    {
        int n = wordList.size();
        visited = vector<bool>(n, false);
        vector<string> path = {beginWord};

        if (dfs(beginWord, endWord, wordList, path) == true)
            return path;
        return vector<string>{};
    }