从Leetcode 每日一题练习继续讨论：
1415. 长度为 n 的开心字符串中字典序第 k 小的字符串
1415. The k-th Lexicographical String of All Happy Strings of Length n
题解
本题可以使用回溯法来尝试构建所有可能的满足题目条件的字符串组合，由于构建过程中在每个位置遍历字符是依照字典序遍历的，因此构建过程最终得到的达到题目要求长度的字符串天然满足字典序。则在构建过程中，一旦长度达到要求长度就将计数加一，当计数达到k时直接返回当前构建得到的字符串。否则返回空字符串。
代码
class Solution {
public:
string getHappyString(int n, int k) {
string current_string;
string result;
int count = 0;
backtrack(n, k, current_string, count, result);
return result;
}
private:
void backtrack(int n, int k, string& current_string, int& count, string& result) {
if (current_string.length() == n) {
count++;
if (count == k) {
result = current_string;
}
return;
}
for (char c : {'a', 'b', 'c'}) {
if (current_string.empty() || current_string.back() != c) {
current_string.push_back(c);
backtrack(n, k, current_string, count, result);
current_string.pop_back();
if (count == k) {
return;
}
}
}
}
};