Từ điển người nước ngoài trong C ++

Giả sử có một ngôn ngữ nước ngoài mới và sử dụng bảng chữ cái latin. Tuy nhiên, thứ tự giữa các chữ cái không được biết. Chúng tôi có một danh sách các từ không trống từ từ điển, những từ này được sắp xếp theo từ điển theo các quy tắc của ngôn ngữ mới này. chúng ta phải tìm thứ tự của các chữ cái trong ngôn ngữ này.

Vì vậy, nếu đầu vào là ["wrt", "wrf", "er", "ett", "rftt"], thì đầu ra sẽ là "wertf"

Để giải quyết vấn đề này, chúng tôi sẽ làm theo các bước sau -

• Xác định một bản đồ được gọi là độ

• Xác định một bản đồ được gọi là đồ thị

• n:=kích thước của từ

• để khởi tạo i:=0, khi tôi

  • để khởi tạo j:=0, khi j

    • độ [từ [i, j]]:=0

• để khởi tạo i:=0, khi tôi

  • l:=kích thước tối thiểu của từ [i] và kích thước của từ [i + 1]

  • để khởi tạo j:=0, khi j

    • x:=words [i, j]

    • y:=words [i + 1, j]

    • nếu x không bằng y thì -

      • chèn y vào cuối biểu đồ [x]

      • (tăng độ [y] lên 1)

      • Ra khỏi vòng lặp

• ret:=chuỗi trống

• Xác định một hàng đợi q

• Đối với mỗi cặp khóa-giá trị, nó theo mức độ, hãy thực hiện -

  • nếu giá trị của nó bằng 0, thì -

    • chèn chìa khóa của nó vào q

• while (không phải q trống), do -

  • x:=phần tử đầu tiên của q

  • xóa phần tử khỏi q

  • ret:=ret + x

  • cho mỗi phần tử ngồi trong biểu đồ làm -

    • giảm độ [ngồi] xuống 1

    • nếu độ [ngồi] bằng 0, thì -

      • chèn sit vào q

    • (tăng 1 chỗ ngồi)

• return (nếu kích thước của ret giống với kích thước của độ thì hãy ret, nếu không thì chuỗi trống)

Ví dụ

Hãy cùng chúng tôi xem cách triển khai sau để hiểu rõ hơn -

#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));
}

Đầu vào

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

Đầu ra

wertf