Trong bài toán này, chúng ta được cho một từ điển và hai từ 'start' và 'target'. Nhiệm vụ là tạo một chuỗi (cầu thang) từ từ bắt đầu đến từ mục tiêu, chuỗi được tạo sao cho mỗi từ khác nhau với từ khác chỉ một ký tự và từ đó cũng phải tồn tại trong từ điển. Từ mục tiêu tồn tại trong từ điển và độ dài của tất cả các từ là như nhau. Chương trình sẽ trả về độ dài đường đi ngắn nhất từ start đến target.
Hãy xem ví dụ để hiểu bài toán,
Đầu vào
Từ điển = {‘HEAL’, ‘HATE’, ‘HEAT’, ‘TEAT’, ‘THAT’, ‘WHAT’ , ‘HAIL’ ‘THAE’} Start = ‘HELL’ Target = ‘THAE’Đầu ra
6
Giải thích
HELL - HEAL - HEAT - TEAT - THAT - THAE
Để giải bài toán này, chúng ta sẽ thực hiện tìm kiếm theo chiều rộng (BFS) của từ điển. Bây giờ, từng bước tìm tất cả các phần tử khác một ký tự từ ký tự trước. Và tạo cầu thang từ start đến target.
Chương trình triển khai giải pháp,
Ví dụ
#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<<"Độ dài chuỗi ngắn nhất từ '"<<start<<"' đến '"<<target<<"' là: "<<wordLadder(start, target, dictionary); return 0; }Đầu ra
Độ dài chuỗi ngắn nhất từ 'hell' đến 'thae' là: 6