พจนานุกรมคนต่างด้าวใน C ++

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

ดังนั้น หากอินพุตเป็น ["wrt","wrf","er", "ett", "rftt" ] เอาต์พุตจะเป็น "wertf"

เพื่อแก้ปัญหานี้ เราจะทำตามขั้นตอนเหล่านี้ -

• กำหนดหนึ่งแผนที่เรียกว่าดีกรี

• กำหนดหนึ่งแผนที่เรียกว่ากราฟ

• n :=ขนาดของคำ

• สำหรับการเริ่มต้น i :=0 เมื่อ i <ขนาดของคำ อัปเดต (เพิ่ม i ขึ้น 1) ทำ -

  • สำหรับการเริ่มต้น j :=0 เมื่อ j <ขนาดของคำ[i] อัปเดต (เพิ่ม j ทีละ 1) ให้ทำ -

    • องศา[คำ[i, j]] :=0

• สำหรับการเริ่มต้น i :=0 เมื่อ i

  • l :=ขนาดขั้นต่ำของคำ[i] และขนาดของคำ[i + 1]

  • สำหรับการเริ่มต้น j :=0 เมื่อ j

    • x :=คำ[i, j]

    • y :=คำ[i + 1, j]

    • ถ้า x ไม่เท่ากับ y แล้ว −

      • แทรก y ที่ส่วนท้ายของกราฟ[x]

      • (เพิ่มดีกรี[y] ขึ้น 1)

      • ออกจากวง

• ret :=สตริงว่าง

• กำหนดหนึ่งคิว q

• สำหรับแต่ละคีย์-ค่าจับคู่เป็นดีกรี ให้ทำ -

  • หากค่าเท่ากับ 0 แล้ว −

    • ใส่คีย์ของมันลงใน q

• ในขณะที่ (ไม่ใช่ q ว่างเปล่า) ทำ -

  • x :=องค์ประกอบแรกของ q

  • ลบองค์ประกอบออกจาก q

  • ret :=ret + x

  • สำหรับแต่ละองค์ประกอบนั่งในกราฟทำ -

    • ลดดีกรี[นั่ง] 1

    • ถ้าดีกรี[นั่ง] เท่ากับ 0 แล้ว −

      • แทรกนั่งลงใน q

    • (เพิ่มขึ้นนั่ง 1)

• return (ถ้าขนาดของ ret เท่ากับขนาดของดีกรี แล้ว ret มิฉะนั้น สตริงที่ว่างเปล่า)

ตัวอย่าง

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

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

อินพุต

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

ผลลัพธ์

wertf