単語がC++で並べ替えられていると見なすことができるようにアルファベット順を検索します

単語の配列があるとすると、英語のアルファベットのアルファベット順を見つけて、指定された単語が昇順で並べ替えられていると見なすことができるようにする必要があります。そのような順序が存在する場合は、「不可能」を返します。

したがって、入力がwords =["efgh"、 "wxyz"]の場合、出力はzyxvutsrqponmlkjihgfewdcba

これを解決するには、次の手順に従います-

• アルファベット：=26
• n：=vのサイズ
• nが1と同じ場合、-
  • 「abcdefghijklmnopqrstuvwxyz」を表示します
  • 戻る
• サイズがALPHABETの配列調整を定義します
• サイズがALPHABETの配列を定義し、0で埋めます
• pre：=v [0]
• iを初期化する場合：=1、i
• s：=v [i]
• 0から最小（preのサイズとsのサイズ）の範囲のjの場合-1 −
  • s[j]がpre[j]と等しくない場合、-
    • ループから抜け出す
  • j
  • s[j]を挿入-adjの最後に「a」のASCII[pre[j]-「a」のASCII]
• in [s [j] --ASCIIof'a']を1増やします
• 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