Bậc thang từ trong C++

Cho beginWord, endWord và danh sách từ wordList. Tìm độ dài chuỗi biến đổi ngắn nhất từ beginWord đến endWord:

• Mỗi bước chỉ đổi 1 chữ cái.
• Từ trung gian phải có trong wordList.

Trả về 0 nếu không thể. Từ cùng độ dài, chữ thường, không trùng lặp.

Ví dụ: begin="hit", end="cog", wordList=["hot","dot","dog","lot","log","cog"] → Kết quả: 5 (hit→hot→dot→dog→cog).

Giải thuật (BFS + Mẫu trung gian)

1. Hàm putStar(j, s): thay ký tự thứ j bằng '*' tạo mẫu.
2. Xây map m: mẫu → danh sách từ khớp.
3. BFS từ (beginWord, 1):
4. Với mỗi từ, sinh mọi mẫu bằng putStar.
5. Với mỗi từ láng giềng trong m[mẫu]: nếu là endWord → trả về level+1; nếu chưa thăm → push (từ, level+1).
6. Trả về 0 nếu hết hàng đợi.

Ví dụ 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++)
            temp += (i == j) ? "*" : string(1, s[i]);
        return temp;
    }
    int ladderLength(string b, string e, vector<string>& w) {
        if(find(w.begin(), w.end(), e) == w.end() || b.empty() || e.empty() || w.empty()) return 0;
        map<string, vector<string>> m;
        for(string x : w)
            for(int j = 0; j < x.size(); j++)
                m[putStar(j, x)].push_back(x);
        queue<pair<string,int>> q;
        q.push({b, 1});
        map<string, int> visited;
        while(!q.empty()) {
            auto [x, l] = q.front(); q.pop();
            for(int i = 0; i < x.size(); i++) {
                string temp = putStar(i, x);
                for(string aa : m[temp]) {
                    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);
    return 0;
}

Đầu vào

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

Đầu ra

5