【程序员面试金典】面试题 17.22 . 单词转换

题目描述

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

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

示例 1:

输入:
beginWord = "hit",
endWord = "cog",
wordList = ["hot","dot","dog","lot","log","cog"]

输出:
["hit","hot","dot","lot","log","cog"]

示例 2:

输入:
beginWord = "hit"
endWord = "cog"
wordList = ["hot","dot","dog","lot","log"]

输出: []

解释: endWord "cog" 不在字典中，所以不存在符合要求的转换序列。

解题思路

思路：最直观的想法是，dfs+回溯。首先依次判断初始字符串是否和单词列表中的各个单词只相差一个字符，如果只相差一个字符则可以进行dfs遍历，如果某一次dfs即成功则直接返回；dfs的过程中依次判断当前字符串是否和单词列表中的尚未访问的各个单词只相差一个字符，如果只相差一个字符则进行dfs，如果某一次dfs成功则直接返回，反之进行回溯。

class Solution {
public:
    vector<string> res;
    bool flag=false;
    //比较s1和s2是否只相差一个字符
    bool compare(string s1,string s2)
    {
        if(s1.size()!=s2.size())
            return false;
        int cnt=0;
        for(int i=0;i<s1.size();i++)
            if(s1[i]!=s2[i])
                cnt++;
        return cnt==1;
    }
    void dfs(string curword,string endWord,vector<string>& wordList,vector<bool> &visited,int n,int index)
    {
        res.push_back(curword);
        visited[index]=true;
        if(curword==endWord)
        {
            flag=true;
            return;
        }
        //依次判断当前字符串是否和单词列表中的尚未访问的各个单词只相差一个字符
        for(int i=0;i<n;i++)
        {
            if(!visited[i]&&compare(curword,wordList[i]))
            {
            	//如果只相差一个字符则进行dfs
                dfs(wordList[i],endWord,wordList,visited,n,i);
                //如果某一次dfs成功则直接返回
                if(flag)
                    return;
                //反之进行回溯
                visited[index]=false;
                res.pop_back();
            }
        }
    }
    vector<string> findLadders(string beginWord, string endWord, vector<string>& wordList) 
    {
        int n=wordList.size();
        //标记数组 用于标记当前字符串是否被访问过
        vector<bool> visited(n,false);
        res.push_back(beginWord);
        //依次判断初始字符串是否和单词列表中的各个单词只相差一个字符
        for(int i=0;i<n;i++)
        {
        	//如果只相差一个字符则可以进行dfs遍历
            if(compare(beginWord,wordList[i]))
            {
                dfs(wordList[i],endWord,wordList,visited,n,i);
                //如果某一次dfs即成功则直接返回
                if(flag)
                    return res;
            }
        }
        //均没有成功则返回空数组
        return vector<string>();
    }
};

总结：注意思考的过程，先按照思路完成，再考虑超时优化。