diff options
-rw-r--r-- | kth_lex_str_happy_n.c | 41 | ||||
-rw-r--r-- | kth_lex_str_happy_n.py | 41 |
2 files changed, 82 insertions, 0 deletions
diff --git a/kth_lex_str_happy_n.c b/kth_lex_str_happy_n.c new file mode 100644 index 0000000..21178ea --- /dev/null +++ b/kth_lex_str_happy_n.c @@ -0,0 +1,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 +} diff --git a/kth_lex_str_happy_n.py b/kth_lex_str_happy_n.py new file mode 100644 index 0000000..2eb9c5f --- /dev/null +++ b/kth_lex_str_happy_n.py @@ -0,0 +1,41 @@ +# 1415. The k-th Lexicographical String of All Happy Strings of Length n + +""" +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'. +""" + + +class Solution(object): + def getHappyString(self, n, k): + """ + :type n: int + :type k: int + :rtype: str + """ + m = n + + def dfs(prefix, n, k): + if n == 0: + return prefix + for c in "abc": + if prefix and c == prefix[-1]: + continue + cnt = 2 ** (m - len(prefix) - 1) + if cnt >= k: + return dfs(prefix + c, n - 1, k) + else: + k -= cnt + return "" + + return dfs("", n, k) + + +if __name__ == "__main__": + obj = Solution() + print(obj.getHappyString(1, 3)) + print(obj.getHappyString(1, 4)) + print(obj.getHappyString(3, 9)) |