Leetcode 1415:长度为n的开心字符串中字典序第k小的字符串(超详细的解法!!!)
in leetcode with 0 comment

Leetcode 1415:长度为n的开心字符串中字典序第k小的字符串(超详细的解法!!!)

in leetcode with 0 comment

一个 「开心字符串」定义为:

比方说,字符串 "abc""ac","b""abcbabcbcb" 都是开心字符串,但是 "aa""baa""ababbc" 都不是开心字符串。

给你两个整数 nk ,你需要将长度为 n 的所有开心字符串按字典序排序。

请你返回排序后的第 k 个开心字符串,如果长度为 n 的开心字符串少于 k 个,那么请你返回 空字符串

示例 1:

输入:n = 1, k = 3
输出:"c"
解释:列表 ["a", "b", "c"] 包含了所有长度为 1 的开心字符串。按照字典序排序后第三个字符串为 "c" 。

示例 2:

输入:n = 1, k = 4
输出:""
解释:长度为 1 的开心字符串只有 3 个。

示例 3:

输入:n = 3, k = 9
输出:"cab"
解释:长度为 3 的开心字符串总共有 12 个 ["aba", "abc", "aca", "acb", "bab", "bac", "bca", "bcb", "cab", "cac", "cba", "cbc"] 。第 9 个字符串为 "cab"

示例 4:

输入:n = 2, k = 7
输出:""

示例 5:

输入:n = 10, k = 100
输出:"abacbabacb"

提示:

解题思路

首先比较容易想到暴力解法,也就是枚举所有可能的结果,枚举到第k个字符串的时候就结束。

class Solution:
    def getHappyString(self, n: int, k: int) -> str:
        res = None

        def dfs(s):
            nonlocal k, res
            if len(s) == n:
                k -= 1 
                if k == 0: res = s
                return
  
            for c in ['a', 'b', 'c']:
                if not s or c != s[-1]:
                    dfs(s + c)
        
        dfs("")
        return "" if not res else res

需要注意的是,枚举字符串的时候我们需要从小的字符像大的字符枚举,这样可以保证枚举的字符串符合字典序。

其实我们可以思考一下总共会出现$3*2^{n-1}$个字符串(第一个位置三种选法,后面位置都是两种选法),那么如果$k>3*2^{n-1}$必然就无解了。对于首字母是'a''b'或者'c'的字符串来说,它们都有$2^{n-1}$中可能,那么可以通过$\frac{k}{2^{n-1}}$确定第一个字母是什么。

接着考虑下一个字符,此时$k=k\% 2^{n-1}$,对于当前字母是'a''b'或者'c'(注意其中一个不合法)的字符串来说,它们都有$2^{n-2}$中可能。如果$k/2^{n-2}=0$并且前一个字符是'a'的话,那么下一个字符就是'b'(保证和前一个字符不同的情况下,实现字符串的最小字典序);如果前一个字符不是'a',那么下一个字符就是'a'。如果$k/2^{n-2}\neq 0$并且前一个字符是'c'的话,那么下一个字符就是'b';如果前一个字符不是'c'的话,那么下一个字符就是'c'。以此类推,可以确定后续的所有字符。

class Solution:
    def getHappyString(self, n: int, k: int) -> str:
        prem = 1 << (n - 1)
        if prem * 3 < k: return ""
        
        k -= 1
        s = chr(97 + k // prem)
        while prem > 1:
            k %= prem
            prem >>= 1
            s += chr(97 + int(s[-1] == 'a')) if k // prem == 0 else chr(98 + int(s[-1] != 'c'))
        return s

reference:

https://leetcode.com/problems/the-k-th-lexicographical-string-of-all-happy-strings-of-length-n/discuss/585590/C%2B%2B-DFS-and-Math

我将该问题的其他语言版本添加到了我的GitHub Leetcode

如有问题,希望大家指出!!!

「如果我的文章对你有很大帮助,那么不妨~!」

coordinate

谢谢老板O(∩_∩)O~

使用微信扫描二维码完成支付

Responses