ค้นหาการเรียงตามตัวอักษรเพื่อให้พิจารณาการจัดเรียงคำในภาษา C++

สมมติว่าเรามีคำศัพท์หลายชุด เราต้องหาลำดับตัวอักษรในตัวอักษรภาษาอังกฤษเพื่อที่คำที่กำหนดจะถูกพิจารณาว่าเรียงลำดับจากน้อยไปมาก หากมีลำดับดังกล่าวอยู่ มิฉะนั้นให้คืนค่า "เป็นไปไม่ได้"

ดังนั้น หากอินพุตเป็นเหมือนคำ =["efgh", "wxyz"] เอาต์พุตจะเป็น zyxvutsrqponmlkjihgfewdcba

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

• ALPHABET :=26
• n :=ขนาดของวี
• ถ้า n เหมือนกับ 1 แล้ว −
  • แสดง "abcdefghijklmnopqrstuvwxyz"
  • คืนสินค้า
• กำหนด adj ของอาร์เรย์ขนาด ALPHABET
• กำหนดอาร์เรย์ขนาด ALPHABET และเติมด้วย 0
• ก่อน :=v[0]
• สำหรับการเริ่มต้น i :=1 เมื่อฉัน
• s :=v[i]
• สำหรับ j ในช่วง 0 ถึงต่ำสุด (ขนาดก่อนและขนาดของ s) - 1 −
  • ถ้า s[j] ไม่เท่ากับ pre[j] แล้ว −
    • ออกมาจากวงจร
  • ถ้า j <ขั้นต่ำของขนาดพรีและขนาดของ s แล้ว −
    • ใส่ s[j] - ASCII ของ 'a' ต่อท้าย adj[pre[j] - ASCII ของ 'a']
  • เพิ่มขึ้นใน[s[j] - ASCII ของ 'a'] ขึ้น 1
  • ก่อน :=s
  • ไม่ต้องสนใจตอนต่อไป ข้ามไปที่ตอนต่อไป
• ถ้าขนาดของพรี> ขนาดของ s แล้ว −
  • แสดง "เป็นไปไม่ได้"
  • คืนสินค้า
• ก่อน :=s

ตัวอย่าง

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

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

อินพุต

{"efgh", "wxyz"}

ผลลัพธ์

zyxvutsrqponmlkjihgfewdcba