Giả sử chúng ta có một chuỗi. Chúng ta sẽ gọi đó là một chuỗi hạnh phúc khi nó chỉ bao gồm các chữ cái ['a', 'b', 'c'] và s [i]! =S [i + 1] cho tất cả các giá trị của i từ 1 đến độ dài của s - 1 (ở đây chuỗi được lập chỉ mục 1).
Vì vậy, nếu chúng ta có hai số nguyên n và k, hãy xem xét một danh sách tất cả các chuỗi hạnh phúc có độ dài n được sắp xếp theo thứ tự từ vựng. Chúng ta phải tìm chuỗi thứ k của danh sách này hoặc trả về một chuỗi rỗng nếu có ít hơn k chuỗi hạnh phúc có độ dài n
Vì vậy, nếu đầu vào là n =3 và k =9, thì đầu ra sẽ là "cab", có 12 chuỗi hạnh phúc khác nhau, đó là ["aba", "abc", "aca", "acb", "bab", "bac", "bca", "bcb", "cab", "cac", "cba", "cbc"], câu thứ 9 là "cab".
Để giải quyết vấn đề này, chúng tôi sẽ làm theo các bước sau -
-
Xác định ret mảng
-
Xác định một hàm giải quyết (), điều này sẽ mất s, l khởi tạo nó bằng 1,
-
nếu l giống với x, thì -
-
chèn s vào cuối ret
-
trở lại
-
-
để khởi tạo i:=0, khi i <3, hãy cập nhật (tăng i lên 1), thực hiện -
-
nếu phần tử cuối cùng của s không bằng c [i] thì -
-
giải quyết (s + c [i], l + 1)
-
-
-
Từ phương thức chính, thực hiện như sau -
-
x:=n
-
nếu n giống 0 thì -
-
trả về chuỗi trống
-
-
giải quyết ("a")
-
giải quyết ("b")
-
giải quyết ("c")
-
sắp xếp lại mảng
-
return (nếu k> kích thước của ret thì chuỗi trống, nếu không thì ret [k - 1])
Ví dụ
Hãy cùng chúng tôi xem cách triển khai sau để hiểu rõ hơn -
#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));
} Đầu vào
3,9
Đầu ra
cab