พจนานุกรมสิ่งมีชีวิตต่างดาวใน C++

สมมติว่ามีภาษาต่างดาวใหม่ที่ใช้ตัวอักษรละติน แต่ลำดับของตัวอักษรไม่ทราบ เรามีรายการคำจากพจนานุกรมที่เรียงลำดับตามกติกาของภาษานี้ เราต้องหาลำดับของตัวอักษรในภาษานี้

เช่น ถ้าอินพุตคือ ["wrt","wrf","er","ett","rftt"] ผลลัพธ์จะเป็น "wertf"

ในการแก้ปัญหานี้ เราจะใช้ Topological Sort (Kahn's Algorithm) ทำตามขั้นตอน:

• สร้าง map degree (indegree) และ graph (adjacency list) จากตัวอักษรทั้งหมด
• เปรียบเทียบคำติดกันคู่: หาตัวอักษรแรกที่ต่างกัน x,y เพิ่ม edge x->y, degree[y]++
• Queue ใส่ตัวอักษรที่ indegree=0; while queue ไม่ว่าง: pop x, เพิ่ม x ในผลลัพธ์; ลด indegree ของเพื่อนบน y ถ้าเป็น 0 ใส่ queue
• ถ้าผลลัพธ์มีความยาวเท่าจำนวนตัวอักษรทั้งหมด คืนค่าผลลัพธ์ มิฉะนั้นคืนค่าว่าง (มี cycle)

ตัวอย่าง

ลองดูการใช้งานต่อไปนี้เพื่อความเข้าใจที่ดีขึ้น:

#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
    string alienOrder(vector& words) {
        map degree;
        map> graph;
        int n = words.size();
        for(int i=0;i q;
        for(auto& it: degree) if(it.second==0) q.push(it.first);
        while(!q.empty()){
            char x=q.front(); q.pop(); ret+=x;
            for(char y: graph[x]){
                degree[y]--;
                if(degree[y]==0) q.push(y);
            }
        }
        return ret.size()==degree.size() ? ret : "";
    }
};
main(){
    Solution ob;
    vector v = {"wrt","wrf","er","ett","rftt"};
    cout << (ob.alienOrder(v));
}

อินพุต

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

เอาต์พุต

wertf