Từ điển ngoại星 trong C++

Có ngôn ngữ ngoài hành tinh dùng bảng chữ cái Latinh nhưng thứ tự chữ cái khác. Cho danh sách từ đã sắp xếp theo thứ tự từ điển của ngôn ngữ đó. Tìm thứ tự các chữ cái.

Ví dụ: ["wrt","wrf","er","ett","rftt"] → "wertf"

Phương pháp giải

Xây dựng đồ thị phụ thuộc từ cặp từ liền kề: tìm ký tự khác nhau đầu tiên, thêm cạnh x→y (x trước y). Tính bậc vào (in-degree). Topological sort (Kahn): hàng đợi các nút bậc vào 0, lấy ra, giảm bậc vào hàng xóm. Nếu kết quả có đủ số chữ cái thì hợp lệ.

Ví dụ chương trình

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

class Solution {
public:
    string alienOrder(vector& words) {
        map degree;
        map> graph;
        
        for (string& w : words)
            for (char c : w) degree[c] = 0;
        
        int n = words.size();
        for (int i = 0; i < n - 1; i++) {
            int l = min(words[i].size(), words[i+1].size());
            for (int j = 0; j < l; j++) {
                char x = words[i][j], y = words[i+1][j];
                if (x != y) {
                    graph[x].push_back(y);
                    degree[y]++;
                    break;
                }
            }
        }
        
        string ret = "";
        queue q;
        for (auto& p : degree) if (p.second == 0) q.push(p.first);
        
        while (!q.empty()) {
            char x = q.front(); q.pop();
            ret += x;
            for (char y : graph[x]) {
                if (--degree[y] == 0) q.push(y);
            }
        }
        return ret.size() == degree.size() ? ret : "";
    }
};

int main() {
    Solution ob;
    vector v = {"wrt","wrf","er","ett","rftt"};
    cout << ob.alienOrder(v);
    return 0;
}

Đầu vào

{"wrt","wrf","er","ett","rftt"}

Đầu ra

wertf