C++での長さnのすべての幸せな文字列のk番目の辞書式文字列

文字列があるとします。 ['a'、'b'、'c']の文字のみで構成され、1からs-1（ここでは文字列は1-インデックス付きです）。

したがって、2つの整数nとkがある場合は、辞書式順序で並べ替えられた長さnのすべての幸せな文字列のリストを検討してください。このリストのk番目の文字列を見つけるか、長さnの幸せな文字列がk個未満の場合は空の文字列を返す必要があります

したがって、入力がn=3およびk=9の場合、出力は「cab」になり、12の異なるハッピーストリングがあります。これらは、["aba"、 "abc"、 "aca"、 "acb"、 「bab」、「bac」、「bca」、「bcb」、「cab」、「cac」、「cba」、「cbc」]、9番目は「cab」です。

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

• 配列retを定義する

• 関数solve（）を定義します。これにはsが必要です、lは1で初期化します

• lがxと同じ場合、-

  • retの最後にsを挿入します

  • 戻る

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

  • sの最後の要素がc[i]と等しくない場合、-

    • 解決（s + c [i]、l + 1）

• メインの方法から、次のようにします-

• x：=n

• nが0と同じ場合、-

  • 空の文字列を返す

• 解決（ "a"）

• 解決（ "b"）

• 解決（ "c"）

• 配列を並べ替えますret

• return（k> retのサイズの場合は空白の文字列、それ以外の場合はret [k-1]）

例

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

#include <bits/stdc++.h>
using namespace std;
struct Cmp{
   bool operator()(string& a, string& b) {
      return !(a < b);
   }
};
char c[3] = {'a', 'b', 'c'};
class Solution {
public:
   vector<string> ret;
   int x;
   void solve(string s, int l = 1){
      if (l == x) {
         ret.push_back(s);
         return;
      }
      for (int i = 0; i < 3; i++) {
         if (s.back() != c[i]) {
            solve(s + c[i], l + 1);
         }
      }
   }
   string getHappyString(int n, int k){
      x = n;
      if (n == 0)
         return "";
      solve("a");
      solve("b");
      solve("c");
      sort(ret.begin(), ret.end());
      return k > ret.size() ? "" : ret[k - 1];
   }
};
main(){
   Solution ob;
   cout << (ob.getHappyString(3,9));
}

入力

3,9

出力

cab