資料結構
網路
關係資料庫管理系統
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理
化學
生物
數學
英語
經濟
心理學
社會研究
時裝設計
法律研究詞階梯（達到目標詞的最短鏈長度）C++
在此問題中，我們給定一個字典和兩個單詞“start”和“target”。我們的任務是生成一個從 start 單詞到 target 單詞的鏈（梯子），其中建立的鏈路使每個單詞都只與另一個單詞相差一個單詞，並且該單詞也應該存在於字典中。目標單詞存在於字典中，並且所有單詞的長度也相同。程式將返回從 start 到 target 的最短路徑的長度。
我們來看一個示例以理解問題，
輸入
Dictionary = {‘HEAL’, ‘HATE’, ‘HEAT’, ‘TEAT’, ‘THAT’, ‘WHAT’ , ‘HAIL’ ‘THAE’}
Start = ‘HELL’
Target = ‘THAE’輸出
6
說明
HELL - HEAL - HEAT - TEAT - THAT - THAE
為了解決此問題，我們將會對字典進行廣度優先搜尋。現在，逐步查詢與前一個單詞相差一字母的所有元素。並建立一個從 start 到 target 的梯子。
展示我們解決方案實現的程式，
示例
#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
更新於：17-Jul-2020
249 次瀏覽
廣告