[CareerCup] 18.10 Word Transform 单词转换

18.10 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.

这道题让我们将一个单词转换成另一个单词，每次只能改变一个字母，让我们输出中间转换过程的单词。LeetCode上有类似的题目One Edit Distance和Edit Distance。我们的方法是写一个get_one_edit_words()函数，来返回某一个单词变动一个字母的所有可能情况，然后我们在transform函数中先将开始的单词存入一个队列queue中，还需要一个set来记录所有访问过的单词，还需要哈希表来建立当前单词和变换一步后的单词之间的映射，然后开始类似BFS的遍历，对于每一个单词，遍历get_one_edit_words()函数返回的结果，如果变换后的单词就是目标单词，则我们完成了变换，根据backtrack将整个路径上的单词存入结果中，如果变换单词不是目标单词，但是在字典中，如果没有在字典中，则我们将其排入queue，并加入visited，和建立哈希表的映射，继续遍历，参见代码如下：

set<string> get_one_edit_words(string word) {

    set<string> res;

    for (int i = ; i < word.size(); ++i) {

        string t = word;

        for (char c = 'a'; c <= 'z'; ++c) {

            if (c != word[i]) {

                t[i] = c;

                res.insert(t);

            }

        }

    }

    return res;

}

vector<string> transform(string start, string end, set<string> dict) {

    queue<string> q;

    set<string> visited;

    unordered_map<string, string> backtrack;

    q.push(start);

    visited.insert(start);

    while (!q.empty()) {

        string w = q.front(); q.pop();

        for (string v : get_one_edit_words(w)) {

            if (v == end) {

                vector<string> res{v};

                while (!w.empty()) {

                    res.insert(res.begin(), w);

                    w = backtrack[w];

                }

                return res;

            }

            if (dict.count(v)) {

                if (!visited.count(v)) {

                    q.push(v);

                    visited.insert(v);

                    backtrack[v] = w;

                }

            }

        }

    }

    return {};

}

类似题目：

One Edit Distance

Edit Distance

CareerCup All in One 题目汇总

巴特西

[CareerCup] 18.10 Word Transform 单词转换

最新文章

热门文章