Word Ladder ใน C++

กำหนดคำเริ่มต้น beginWord, คำสิ้นสุด endWord และรายการคำในพจนานุกรม wordList หาความยาวลำดับการเปลี่ยนแปลงสั้นที่สุดจาก beginWord ถึง endWord โดย:

• เปลี่ยนได้เพียงตัวอักษรเดียวในแต่ละขั้นตอน
• คำที่เปลี่ยนแล้วต้องอยู่ใน wordList (beginWord ไม่ถือเป็นคำที่เปลี่ยนแล้ว)

เงื่อนไข: คืน 0 ถ้าไม่มีลำดับ, คำทุกคำยาวเท่ากัน, มีแต่ตัวพิมพ์เล็ก, ไม่มีคำซ้ำใน wordList

ตัวอย่าง: beginWord = "hit", endWord = "cog", wordList = ["hot","dot","dog","lot","log","cog"]
ผลลัพธ์: 5 (hit → hot → dot → dog → cog)

ขั้นตอนการแก้ปัญหา (BFS + Generic States)

• ฟังก์ชัน putStar(j, s) คืนสตริงที่แทนที่ตัวอักษรตำแหน่ง j ด้วย '*'
• สร้างแผนที่ m จาก generic state (เช่น "h*t") ไปยังรายการคำที่ตรงกัน
• BFS เริ่มจาก (beginWord, 1):
  • สำหรับแต่ละตำแหน่ง i สร้าง generic state
  • สำหรับแต่ละคำใน m[state] ถ้ายังไม่ได้เยี่ยม ใส่คิวพร้อมระดับ+1
  • ถ้าพบ endWord คืนระดับ+1
• คืน 0 ถ้าไม่พบ

ตัวอย่างโค้ด (C++)

#include <bits/stdc++.h> 
using namespace std; 

class Solution {
public:
    string putStar(int j, string s) {
        string temp = "";
        for(int i = 0; i < s.size(); i++) {
            if(i == j) temp += "*";
            else temp += s[i];
        }
        return temp;
    }
    int ladderLength(string b, string e, vector<string>& w) {
        if(find(w.begin(), w.end(), e) == w.end() || !b.size() || !e.size() || !w.size()) return 0;
        map < string , vector <string> > m;
        for(int i = 0; i < w.size(); i++) {
            string x = w[i];
            for(int j = 0; j < x.size(); j++) {
                string inter = putStar(j, x);
                m[inter].push_back(x);
            }
        }
        queue < pair <string, int> > q;
        q.push({b, 1});
        map <string, int> visited;
        while(!q.empty()) {
            pair < string, int > s = q.front();
            q.pop();
            string x = s.first;
            int l = s.second;
            for(int i = 0; i < x.size(); i++) {
                string temp = putStar(i, x);
                for(int j = 0; j < m[temp].size(); j++) {
                    string aa = m[temp][j];
                    if(aa == e) return l + 1;
                    if(!visited[aa]) {
                        q.push({aa, l + 1});
                        visited[aa] = 1;
                    }
                }
            }
        }
        return 0;
    }
};

int main() {
    vector<string> v = {"hot","dot","dog","lot","log","cog"};
    Solution ob;
    cout << (ob.ladderLength("hit", "cog", v));
}

อินพุต

"hit" "cog" ["hot","dot","dog","lot","log","cog"]

เอาต์พุต

5