1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
|
// 1415. The k-th Lexicographical String of All Happy Strings of Length n
#include "leetcode.h"
/*
* a happy string is a string that consists only of letters of the set '[a, b,
* c]', 's[i] != s[i + 1]' for all values of 'i' from 1 to 's.length - 1'. given
* two integers 'n' and 'k', consider a list of all happy strings of length 'n'
* sorted in lexicographical order. return the k'th string of this list or
* return an empty string if there are less than 'k' strings of length 'n'.
*/
char *dfs(char *prefix, int n, int m, int *k) {
if (!n)
return prefix;
for (char c = 'a'; c <= 'c'; c++) {
int n = strlen(prefix);
if (n && c == prefix[n - 1])
continue;
int cnt = (int)pow(2, m - n - 1);
if (cnt >= *k) {
prefix[n] = c;
prefix[n + 1] = '\0';
return dfs(prefix, n - 1, m, k);
} else
*k -= cnt;
}
return "";
}
char *getHappyString(int n, int k) {
int m = n;
char *prefix = (char *)malloc((n + 1) * sizeof(char));
prefix[0] = '\0';
return dfs(prefix, n, m, &k);
}
int main() {
printf("%s\n", getHappyString(1, 3)); // expect: c
printf("%s\n", getHappyString(1, 4)); // expect: null
printf("%s\n", getHappyString(3, 9)); // expect: cab
}
|