在这个问题中,我们得到了一个字典和两个单词“ start”和“ target”。我们的任务是生成从开始工作到目标单词的链(梯子),创建该链以使每个单词仅将一个单词与另一个字符区别开,并且该单词也应存在于词典中。目标词存在于字典中,并且所有词的长度都相同。程序将返回从起点到目标的最短路径的长度。
让我们举个例子来了解这个问题,
Dictionary = {‘HEAL’, ‘HATE’, ‘HEAT’, ‘TEAT’, ‘THAT’, ‘WHAT’ , ‘HAIL’ ‘THAE’} Start = ‘HELL’ Target = ‘THAE’
输出结果
6
HELL - HEAL - HEAT - TEAT - THAT - THAE
为了解决这个问题,我们将对字典进行广度优先搜索。现在,逐步查找与前一个字符相距一个字母的所有元素。并从头到尾创建一个阶梯。
展示我们解决方案实施情况的程序,
#include <bits/stdc++.h> using namespace std; int wordLadder(string start, string target, set<string>& dictionary) { if (dictionary.find(target) == dictionary.end()) return 0; int level = 0, wordlength = start.size(); queue<string> ladder; ladder.push(start); while (!ladder.empty()) { ++level; int sizeOfLadder = ladder.size(); for (int i = 0; i < sizeOfLadder; ++i) { string word = ladder.front(); ladder.pop(); for (int pos = 0; pos < wordlength; ++pos) { char orig_char = word[pos]; for (char c = 'a'; c <= 'z'; ++c) { word[pos] = c; if (word == target) return level + 1; if (dictionary.find(word) == dictionary.end()) continue; dictionary.erase(word); ladder.push(word); } word[pos] = orig_char; } } } return 0; } int main() { set<string> dictionary; dictionary.insert("heal"); dictionary.insert("heat"); dictionary.insert("teat"); dictionary.insert("that"); dictionary.insert("what"); dictionary.insert("thae"); dictionary.insert("hlle"); string start = "hell"; string target = "thae"; cout<<"Length of shortest chain from '"<<start<<"' to '"<<target<<"' is: "<<wordLadder(start, target, dictionary); return 0; }
输出结果
Length of shortest chain from 'hell' to 'thae' is: 6