Tìm thứ tự bảng chữ cái sao cho các từ có thể được sắp xếp trong C ++

Giả sử chúng ta có một mảng các từ, chúng ta phải tìm bất kỳ thứ tự chữ cái nào trong bảng chữ cái tiếng Anh để các từ đã cho có thể được coi là sắp xếp theo thứ tự tăng dần, nếu có bất kỳ thứ tự nào như vậy tồn tại, nếu không thì trả về "không thể".

Vì vậy, nếu đầu vào giống như words =["efgh", "wxyz"], thì đầu ra sẽ là zyxvutsrqponmlkjihgfewdcba

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

• ALPHABET:=26
• n:=kích thước của v
• nếu n giống 1, thì -
  • hiển thị "abcdefghijklmnopqrstuvwxyz"
  • trở lại
• Xác định điều chỉnh của mảng có kích thước ALPHABET
• Xác định một mảng có kích thước ALPHABET và điền bằng 0
• pre:=v [0]
• để khởi tạo i:=1, khi i
• s:=v [i]
• cho j trong phạm vi từ 0 đến tối thiểu là (kích thước của trước và kích thước của s) - 1 -
  • nếu s [j] không bằng pre [j], thì -
    • Ra khỏi vòng lặp
  • nếu j
  • chèn s [j] - ASCII của 'a' vào cuối adj [pre [j] - ASCII của 'a']
• tăng [s [j] - ASCII của 'a'] thêm 1
• pre:=s
• Bỏ qua phần sau, chuyển sang phần lặp tiếp theo

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;
#define ALPHABET 26
void search_ordering(vector<string> v) {
   int n = v.size();
   if (n == 1) {
      cout << "abcdefghijklmnopqrstuvwxyz";
      return;
   }
   vector<int> adj[ALPHABET];
   vector<int> in(ALPHABET, 0);
   string pre = v[0];
   for (int i = 1; i < n; ++i) {
      string s = v[i];
      int j;
      for (j = 0; j < min(pre.length(), s.length()); ++j)
         if (s[j] != pre[j])
            break;
      if (j < min(pre.length(), s.length())) {
         adj[pre[j] - 'a'].push_back(s[j] - 'a');
         in[s[j] - 'a']++;
         pre = s;
         continue;
      }
      if (pre.length() > s.length()) {
         cout << "Impossible";
         return;
      }
      pre = s;
   }
   stack<int> my_stack;
   for (int i = 0; i < ALPHABET; ++i)
      if (in[i] == 0)
         my_stack.push(i);
   vector<char> out;
   bool vis[26];
   memset(vis, false, sizeof(vis));
   while (!my_stack.empty()) {
      char x = my_stack.top();
      my_stack.pop();
      vis[x] = true;
      out.push_back(x + 'a');
      for (int i = 0; i < adj[x].size(); ++i) {
         if (vis[adj[x][i]])
            continue;
         in[adj[x][i]]--;
         if (in[adj[x][i]] == 0)
            my_stack.push(adj[x][i]);
      }
   }
   for (int i = 0; i < ALPHABET; ++i)
   if (!vis[i]) {
      cout << "Impossible";
      return;
   }
   for (int i = 0; i < out.size(); ++i)
   cout << out[i];
}
int main() {
   vector<string> v{"efgh", "wxyz"};
   search_ordering(v);
}

Đầu vào

{"efgh", "wxyz"}

Đầu ra

zyxvutsrqponmlkjihgfewdcba