【程序员面试金典】面试题 17.22 . 单词转换-Toy模板网

这篇具有很好参考价值的文章主要介绍了【程序员面试金典】面试题 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>();
    }
};

总结：注意思考的过程，先按照思路完成，再考虑超时优化。文章来源地址https://www.toymoban.com/news/detail-514093.html

到了这里，关于【程序员面试金典】面试题 17.22 . 单词转换的文章就介绍完了。如果您还想了解更多内容，请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章，希望大家以后多多支持TOY模板网！