C++py3排列組合與binary表達解Leetcode 1415 The k th Lexicographical String of Al...

C++py3排列組合與binary表達解Leetcode 1415  The k th Lexicographical String of All Happy Strings of Length n

總共有3*2^(n-1)個happy strings要求第k個。先算(k-1)除以2^(n-1)的商q與餘數r，s[0]由q決定，s[1:n]由r決定，化r為二進位，然後簡單處理一下就得解

[Py3解請進]

------------------

There are a total of 3*2^(n-1) happy strings required for the kth one. First calculate the quotient q and remainder r of (k-1) divided by 2^(n-1), s[0] is determined by q, s[1:n] is determined by r, convert r into binary, and then simply process it to get the solution

[codes on Leetcode]https://leetcode.com/problems/the-k-th-lexicographical-string-of-all-happy-strings-of-length-n/solutions/6439753/combinatorics-binary-expression-c-py3-beats-100/

class Solution:
    def getHappyString(self, n: int, k: int) -> str:
        sz=3*(1<<(n-1))
        if k>sz: return ""

        q, r=divmod(k-1, 1<<(n-1))
        s=[' ']*n
        s[0]=chr(ord('a') + q)
        
        B=format(r, f'0{n-1}b')  # Equivalent to bitset<9> bin(r) with n-1 bits

        xx = [['b', 'c'], ['a', 'c'], ['a', 'b']]
        
        for i in range(n-1):  # Iterating from 0 to n-2
            idx=ord(s[i]) - ord('a')
            s[i+1]=xx[idx][1] if B[i]=='1' else xx[idx][0]

        return "".join(s)