查找字母顺序，以便可以将单词视为在C ++中排序

假设我们有一个单词数组，我们必须找到英语字母中的任何字母顺序，以便给定的单词可以被视为以升序排序（如果存在这样的顺序），否则返回“不可能”。

因此，如果输入像单词= [“ efgh”，“ wxyz”]，则输出将为zyxvutsrqponmlkjihgfewdcba

为了解决这个问题，我们将遵循以下步骤-

• 字母：= 26

• n：= v的大小

• 如果n与1相同，则-

• 显示“ abcdefghijklmnopqrstuvwxyz”

• 返回

• 定义大小为ALPHABET的数组adj

• 定义大小为ALPHABET的数组，并填充0

• pre：= v [0]

• 对于初始化i：= 1，当i <n时，更新（将i增加1），-

• 显示“不可能”

• 返回

• 如果s [j]不等于pre [j]，则-

• 如果j <pre的大小和s的大小的最小值，则-

• in [s [j]-'a'的ASCII]增加1

• pre：= s

• 忽略以下部分，跳至下一个迭代

• 从循环中出来

• 在dj [pre [j]-'a'的ASCII]末尾插入s [j]-'a'的ASCII

• s：= v [i]

• 对于范围从0到最小值（pre的大小和s的大小）的j-1 −

• 如果pre的大小> s的大小，则-

• pre：= s

• 定义一个堆栈my_stack

• 对于初始化i：= 0，当i <ALPHABET时，更新（将i增加1），执行-

• 将我插入my_stack

• 如果in [i]等于0，则-

• 定义一个数组

• 定义大小为：的数组。26.用false填充

• 而（my_stack不为空），-

• 显示[i]

• 如果不是vis [i]不为零，则-

• 返回

• 显示“不可能”

• 如果vis [adj [x，i]]不为零，则-

• （将[adj [x，i]]减少1）

• 如果in [adj [x，i]]与0相同，则-

• 忽略以下部分，跳至下一个迭代

• 将adj [x，i]插入my_stack

• x：= my_stack的顶部元素

• 从my_stack中删除元素

• vis [x]：= true

• 在out的末尾插入x + ASCII'a'

• 对于初始化i：= 0，当i <adj [x]的大小时，更新（将i增加1），执行-

• 对于初始化i：= 0，当i <ALPHABET时，更新（将i增加1），执行-

• 对于初始化i：= 0，当i <out of size，更新（将i增加1）时，执行-

例 

让我们看下面的实现以更好地理解-

#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