C++에서 길이가 n인 모든 해피 문자열의 k번째 사전 문자열

문자열이 있다고 가정합니다. 1에서 길이까지 i의 모든 값에 대해 ['a', 'b', 'c'] 문자 및 s[i] !=s[i + 1]으로만 구성된 문자열을 행복한 문자열이라고 부를 것입니다. s - 1(여기서 문자열은 1-인덱싱됨).

따라서 두 개의 정수 n과 k가 있는 경우 사전순으로 정렬된 길이 n의 모든 행복한 문자열 목록을 고려하십시오. 이 목록의 k번째 문자열을 찾거나 길이가 n

따라서 입력이 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 삽입

  • 반환

• initialize i :=0의 경우, i <3일 때 업데이트(i를 1만큼 증가), 수행 -

  • s의 마지막 요소가 c[i]와 같지 않으면 -

    • 풀다(s + c[i], l + 1)

• 기본 방법에서 다음을 수행하십시오 -

• x :=n

• n이 0과 같으면 -

  • 빈 문자열 반환

• 해결("a")

• 해결("b")

• 해결("c")

• ret 배열 정렬

• 반환(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