文章作者：Tyan
博客：noahsnail.com ?|? CSDN ?|? 簡(jiǎn)書(shū)

1. Description

Find Kth Bit in Nth Binary String

2. Solution

解析：Version 1，依次求出Si，返回對(duì)應(yīng)的第k位即可。Version 2進(jìn)行了優(yōu)化，當(dāng)字符串的長(zhǎng)度大于等于k時(shí)，第k位字符就已經(jīng)可以確定并返回了，不需要執(zhí)行到Sn。

• Version 1

class Solution:
    def findKthBit(self, n: int, k: int) -> str:
        pre = '0'
        for i in range(1, n):
            current = pre + '1' + self.invert(pre)[::-1]
            pre = current
        return pre[k-1]


    def invert(self, s):
        result = ''
        for ch in s:
            if ch == '1':
                result += '0'
            else:
                result += '1'
        return result

• Version 2

class Solution:
    def findKthBit(self, n: int, k: int) -> str:
        pre = '0'
        for i in range(1, n):
            if len(pre) < k:
                current = pre + '1' + self.invert(pre)[::-1]
                pre = current
            else:
                return pre[k-1]
        return pre[k-1]


    def invert(self, s):
        result = ''
        for ch in s:
            if ch == '1':
                result += '0'
            else:
                result += '1'
        return result

Reference

1. https://leetcode.com/problems/find-kth-bit-in-nth-binary-string/