C++のエイリアン辞書

新しい異星言語があり、それがラテンアルファベットを使用していると仮定します。ただし、文字間の順序は不明です。辞書にある空でない単語のリストがあります。これらの単語は、この新しい言語の規則に従って辞書式に並べ替えられています。この言語の文字の順序を見つける必要があります。

したがって、入力が["wrt"、 "wrf"、 "er"、 "ett"、 "rftt"]の場合、出力は "wertf"

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

• 次数と呼ばれる1つのマップを定義します

• グラフと呼ばれる1つのマップを定義する

• n：=単語のサイズ

• 初期化i：=0の場合、i <単語のサイズの場合、更新（iを1増やします）、実行-

  • 初期化j：=0の場合、j

    • 度[単語[i、j]]：=0

• 初期化i：=0の場合、i

  • l：=単語の最小サイズ[i]と単語のサイズ[i + 1]

  • 初期化j：=0の場合、j

    • x：=words [i、j]

    • y：=words [i + 1、j]

    • xがyと等しくない場合、-

      • グラフの最後にyを挿入します[x]

      • （次数[y]を1増やします）

      • ループから出てきます

• ret：=空白の文字列

• 1つのキューを定義するq

• キーと値のペアごとに、次のように実行します-

  • その値が0と同じ場合、-

    • そのキーをqに挿入します

• （qが空ではない）間、-

  • x：=qの最初の要素

  • qから要素を削除

  • ret：=ret + x

  • グラフに配置されている要素ごとに-

    • 度[座る]を1つ減らす

    • degree [sit]が0と同じ場合、-

      • 挿入座りをqに挿入

    • （座る回数を1つ増やします）

• return（retのサイズがdegreeのサイズと同じ場合は、ret、それ以外の場合は空白の文字列）

例

理解を深めるために、次の実装を見てみましょう-

#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
   string alienOrder(vector<string>& words) {
      map<char, int> degree;
      map<char, vector<char> > graph;
      int n = words.size();
      for (int i = 0; i < words.size(); i++) {
         for (int j = 0; j < words[i].size(); j++) {
            degree[words[i][j]] = 0;
         }
      }
      for (int i = 0; i < n - 1; i++) {
         int l = min((int)words[i].size(), (int)words[i + 1].size());
         for (int j = 0; j < l; j++) {
            char x = words[i][j];
            char y = words[i + 1][j];
            if (x != y) {
               graph[x].push_back(y);
               degree[y]++;
               break;
            }
         }
      }
      string ret = "";
      queue<char> q;
      map<char, int>::iterator it = degree.begin();
      while (it != degree.end()) {
         if (it->second == 0) {
            q.push(it->first);
         }
         it++;
      }
      while (!q.empty()) {
         char x = q.front();
         q.pop();
         ret += x;
         vector<char>::iterator sit = graph[x].begin();
         while (sit != graph[x].end()) {
            degree[*sit]--;
            if (degree[*sit] == 0) {
               q.push(*sit);
            }
            sit++;
         }
      }
      return ret.size() == degree.size() ? ret : "";
   }
};
main(){
   Solution ob;
   vector<string> v = {"wrt","wrf","er","ett","rftt"};
   cout <<(ob.alienOrder(v));
}

入力

{"wrt","wrf","er","ett","rftt"}

出力

wertf