C ++中的字阶（到达目标字词的最短链条长度）
在这个问题中，我们得到了一个字典和两个单词“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