C++ में वर्ड लैडर (लक्ष्य शब्द तक पहुंचने के लिए सबसे छोटी श्रृंखला की लंबाई)

इस समस्या में, हमें एक डिक्शनरी और दो शब्द '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& dictionary) {
    if (dictionary.find(target) == dictionary.end())
        return 0;
    int level = 0, wordlength = start.size();
    queue 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 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