1415. The k-th Lexicographical String of All Happy Strings of Length n

问题:

求由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 of i from 1 to s.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 };
原文地址:https://www.cnblogs.com/habibah-chang/p/14395008.html