Leetcode 5374:長さnの楽しい文字列の中で辞書順のk番目に小さい文字列

タイトルの説明
「楽しい文字列」は次のように定義されます.

は、小文字['a', 'b', 'c']のみを含む.

は、1からs.length - 1の間のすべてのiに対して、s[i] != s[i + 1]を満たす(文字列の下付き文字は1から始まる).

例えば、文字列「abc」、「ac」、「b」、「abcbabcbcb」は楽しい文字列ですが、「aa」、「baa」、「abababbc」は楽しい文字列ではありません.
2つの整数nとkをあげます.nの長さのすべての楽しい文字列を辞書順にソートする必要があります.
ソート後のk番目の楽しい文字列を返してください.長さnの楽しい文字列がk未満の場合は、空の文字列を返してください.
 
例1:

  ：n = 1, k = 3
  ："c"
  ：   ["a", "b", "c"]          1       。                "c" 。

例2:

  ：n = 1, k = 4
  ：""
  ：    1          3  。

例3:

  ：n = 3, k = 9
  ："cab"
  ：    3           12   ["aba", "abc", "aca", "acb", "bab", "bac", "bca", "bcb", "cab", "cac", "cba", "cbc"] 。  9       "cab"

例4:

  ：n = 2, k = 7
  ：""

例5:

  ：n = 10, k = 100
  ："abacbabacb"

 
ヒント:

1 <= n <= 10

1 <= k <= 100

 
 

class Solution {
public:
    void dfs(int cur,int n,string str,int &curk,int k,string &ans){
        if(cur >= n || curk > k){
            if(cur == n){
                if(++curk == k) ans = str;
            }
            return;
        }
        for(int j=0;j<3;++j){
            char c = j+'a';
            if(cur == 0 || cur>0&&c!=str[cur-1]){
                str += c;
                dfs(cur+1,n,str,curk,k,ans);
                str.pop_back();
            }
        }
    }
    string getHappyString(int n, int k) {
        string ans = "";
        int curk = 0;
        dfs(0,n,"",curk,k,ans);
        return ans;
    }
};