Word Ladder (ความยาวโซ่สั้นที่สุดเพื่อไปถึงคำเป้าหมาย) ใน C++

ในโจทย์นี้ เราได้รับพจนานุกรมและสองคำคือ 'start' และ 'target' งานของเราคือสร้างโซ่ (ladder) จากคำเริ่มต้นไปยังคำเป้าหมาย โซ่ถูกสร้างโดยที่แต่ละคำแตกต่างจากคำก่อนหน้ามากกว่า 1 ตัวอักษร และคำนั้นต้องมีอยู่ในพจนานุกรม คำเป้าหมายมีอยู่ในพจนานุกรม และความยาวของทุกคำเท่ากัน โปรแกรมจะคืนค่าความยาวของเส้นทางสั้นที่สุดจาก start ไป target

ตัวอย่าง

อินพุต

Dictionary = {'HEAL', 'HATE', 'HEAT', 'TEAT', 'THAT', 'WHAT', 'HAIL', 'THAE'}
Start = 'HELL'
Target = 'THAE'

เอาต์พุต

6

คำอธิบาย

HELL -> HEAL -> HEAT -> TEAT -> THAT -> THAE

เพื่อแก้ปัญหานี้ เราจะทำ Breadth-First Search (BFS) ของพจนานุกรม ตอนนี้ทีละขั้นตอน หาองค์ประกอบทั้งหมดที่ห่างจากตัวอักษรก่อนหน้า 1 ตัวอักษร และสร้างลadder จาก 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