问题：
求由n个字符构成，按照字母序排序后，第k个happy string。
happy string定义：
- consists only of letters of the set
[‘a‘, ‘b‘, ‘c‘].- 仅由a，b，c构成
-
s[i] != s[i + 1]for all values ofifrom1tos.length - 1(string is 1-indexed).- 连续两个字符不重复
如："abc", "ac", "b", "abcbabcbcb"
不是happy string的例子："aa", "baa", "ababbc"
Example 1: Input: n = 1, k = 3 Output: "c" Explanation: The list ["a", "b", "c"] contains all happy strings of length 1. The third string is "c". Example 2: Input: n = 1, k = 4 Output: "" Explanation: There are only 3 happy strings of length 1. Example 3: Input: n = 3, k = 9 Output: "cab" Explanation: There are 12 different happy string of length 3 ["aba", "abc", "aca", "acb", "bab", "bac", "bca", "bcb", "cab", "cac", "cba", "cbc"]. You will find the 9th string = "cab" Example 4: Input: n = 2, k = 7 Output: "" Example 5: Input: n = 10, k = 100 Output: "abacbabacb" Constraints: 1 <= n <= 10 1 <= k <= 100
解法：Backtracking（回溯算法）
- 状态：到当前位置pos为止，构成的快乐串path
- 选择：a，b，c中，除了path.back字符之外的两个。
- 退出递归条件：
- path.length==n ->处理k--（找到一个快乐串）
- 得到要求的第k个结果，条件：k==0
代码参考：
1 class Solution { 2 public: 3 void backtrack(string& res, int pos, string path, int& n, int& k) { 4 if(path.length() == n){ 5 k--; 6 if(k==0){ 7 res=path; 8 } 9 return; 10 } 11 for(int i=0; i<3; i++) { 12 char cur = ‘a‘+i; 13 if(‘a‘+i==path.back()) continue; 14 backtrack(res, pos+1, path+cur, n, k); 15 if(k==0) return; 16 } 17 return; 18 } 19 string getHappyString(int n, int k) { 20 string res(""); 21 backtrack(res, 0, string(""), n, k); 22 return res; 23 } 24 };
1415. The k-th Lexicographical String of All Happy Strings of Length n