หาลำดับตัวอักษรให้คำเรียงลำดับได้ใน C++

แนวคิด

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

เช่น ถ้าอินพุตคือ words = ["efgh", "wxyz"] ผลลัพธ์จะเป็น zyxvutsrqponmlkjihgfewdcba

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

• ALPHABET := 26
• n := ขนาดของ v
• ถ้า n เท่ากับ 1 แล้ว:
  • แสดง "abcdefghijklmnopqrstuvwxyz"
  • คืนค่า
• กำหนดอาร์เรย์ adj ขนาด ALPHABET
• กำหนดอาร์เรย์ in ขนาด ALPHABET เติม 0
• pre := v[0]
• วนลูป i := 1 ถึง n-1:
  • s := v[i]
  • วนลูป j จาก 0 ถึง min(ความยาว pre, ความยาว s) - 1:
    • ถ้า s[j] ไม่เท่ากับ pre[j] แล้ว:
      • ออกจากลูป
  • ถ้า j < min(ความยาว pre, ความยาว s) แล้ว:
    • แทรก s[j] - ASCII ของ 'a' ลงท้าย adj[pre[j] - ASCII ของ 'a']
  • เพิ่ม in[s[j] - ASCII ของ 'a'] ขึ้น 1
  • pre := s
  • ข้ามส่วนต่อไป ไปรอบต่อไป
• ถ้าความยาว pre > ความยาว s แล้ว:
  • แสดง "Impossible"
  • คืนค่า
• pre := 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