এই সমস্যায়, আমাদের একটি ডিকশনারি এবং দুটি শব্দ 'start' এবং 'target' দেওয়া আছে। আমাদের কাজ হল start শব্দ থেকে target শব্দে একটি চেইন (ল্যাডার) তৈরি করা, চেইনটি এমনভাবে তৈরি করা হবে যাতে প্রতিটি শব্দ অন্যটির সাথে শুধু এক অক্ষরের পার্থক্য রাখে এবং শব্দটি ডিকশনারিতে থাকতে হবে। টার্গেট শব্দ ডিকশনারিতে আছে এবং সব শব্দের দৈর্ঘ্য একই। প্রোগ্রামটি start থেকে target পর্যন্ত সবচেয়ে ছোট পথের দৈর্ঘ্য রিটার্ন করবে।
একটি উদাহরণ নিয়ে সমস্যাটি বুঝি,
ইনপুট
ডিকশনারি = {'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<<"'"<<start<<"' থেকে '"<<target<<"' পর্যন্ত সবচেয়ে ছোট চেইনের দৈর্ঘ্য: "<<wordLadder(start, target, dictionary); return 0; }
আউটপুট
'hell' থেকে 'thae' পর্যন্ত সবচেয়ে ছোট চেইনের দৈর্ঘ্য: 6
