C ++中长度为n的所有快乐字符串的第k个词法字符串

  • Z时代
  • 2024-01-10
  • 分类：综合

假设我们有一个字符串。当i的所有值（从1到长度为）仅由['a'，'b'，'c']个字母和s [i]！= s [i + 1]组成时，我们将称该字符串为快乐字符串s-1（此处字符串为1索引）。

因此，如果我们有两个整数n和k，请考虑按字典顺序排序的所有长度为n的快乐字符串的列表。我们必须找到此列表的第k个字符串，或者如果少于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进行初始化，用1进行初始化，

  • 如果l与x相同，则-

    • 在ret的末尾插入s

    • 返回

  • 对于初始化i：= 0，当i <3时，更新（将i增加1），执行-

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

    • 如果s的最后一个元素不等于c [i]，则-

  • 从主要方法中，执行以下操作-

  • x：= n

  • 如果n等于0，则-

    • 返回空字符串

  • 解决（“ a”）

  • 解决（“ b”）

  • resolve（“ 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

以上是 C ++中长度为n的所有快乐字符串的第k个词法字符串 的全部内容， 来源链接： utcz.com/z/352422.html

回到顶部