原文链接: https://leetcode-cn.com/problems/word-transformer-lcci

英文原文

Given two words of equal length that are in a dictionary, write a method to transform one word into another word by changing only one letter at a time. The new word you get in each step must be in the dictionary.

Write code to return a possible transforming sequence. If there is more than one sequence, return any of them.

Example 1:

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

Output:
["hit","hot","dot","lot","log","cog"]

Example 2:

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

Output: []

Explanation: endWord "cog" is not in the dictionary, so there's no possible transforming sequence.

中文题目

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

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

示例 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" 不在字典中，所以不存在符合要求的转换序列。

通过代码

高赞题解

解题思路

此处撰写解题思路

代码

class Solution {
public:

    bool canTranslate(string& from_, string& to_){
        if(from_.size() != to_.size()) { return false; }
        int count = 0;
        for(int i = 0; i < from_.size(); ++i){
            if(from_[i] != to_[i]) {
                count++;
            }
        }
        return count == 1;
    }

    bool hasRoute(string& curWord, string& endWord, vector<string>& wordList, 
                    vector<bool>& visited, vector<string>& result) {
        if(curWord == endWord){ return true; }
        for(int i = 0; i < wordList.size(); ++i){
            if(visited[i] || !canTranslate(curWord, wordList[i])) continue;
            visited[i] = true;
            result.push_back(wordList[i]);
            if(hasRoute(wordList[i], endWord, wordList, visited, result)){
                return true;
            }
            result.pop_back();
            // 如果运行到这一步，意味着无法从i这个点找到路径，所以visited[i]无需改为false.
            // visited[i] = false;
        }
        return false;
    }

    vector<string> findLadders(string beginWord, string endWord, vector<string>& wordList) {
        vector<string> result = {beginWord};
        vector<bool> visited(wordList.size(), false);
        if(hasRoute(beginWord, endWord, wordList, visited, result)){
            return result;
        }
        return vector<string>();
    }
};

统计信息

通过次数	提交次数	AC比率
9384	24750	37.9%

提交历史

提交时间	提交结果	执行时间	内存消耗	语言