단어가 C++에서 정렬된 것으로 간주될 수 있도록 알파벳 순서 찾기

단어 배열이 있다고 가정하면 주어진 단어가 오름차순으로 정렬된 것으로 간주될 수 있도록 영어 알파벳에서 알파벳 순서를 찾아야 합니다. 그러한 순서가 존재하는 경우 그렇지 않으면 "불가능"을 반환합니다.

따라서 입력이 단어 =["efgh", "wxyz"]와 같으면 출력은 zyxvutsrqponmlkjihgfewdcba

이 문제를 해결하기 위해 다음 단계를 따릅니다. −

• 알파벳 :=26
• n :=v의 크기
• n이 1과 같으면 -
  • "abcdefghijklmnopqrstuvwxyz" 표시
  • 반환
• ALPHABET 크기의 배열 adj 정의
• ALPHABET 크기의 배열을 정의하고 0으로 채움
• 사전 :=v[0]
• 초기화 i :=1의 경우, i
• :=v[i]
• (pre의 크기와 s의 크기) - 1 −
  범위 0에서 최소값의 j에 대해
  • s[j]가 pre[j]와 같지 않으면 -
    • 루프에서 빠져나오기
  • j
  • insert s[j] - adj[pre[j]의 끝에 'a'의 ASCII - 'a'의 ASCII]
• [s[j] - 'a'의 ASCII를 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