LeetCode Count and Say

LeetCode Count and Say

把一個數字用幾個幾的形式表示出來。如2就是1個2，即12。對12進行數數得到1112，依次類推。假設初始數字是1，求第n個數是什麼。起始5個數字為1, 11, 21, 1211, 111221, …

注意點：

例子：

輸入: n = 5
輸出: 111221

解題思路

用一個下標來表示當前統計的字符的起始位置，一個計數器來表示該字符的數目。不斷讀取直到字符不相等，添加到結果集中，更新起始位置和計數器。下面代碼中的計數器用下標相減代替。

AC源碼

class Solution(object):
    def countAndSay(self, n):
        """
        :type n: int
        :rtype: str
        """
        result = "1"
        for __ in range(1, n):
            result = self.getNext(result)
        return result

    def getNext(self, s):
        result = []
        start = 0
        while start < len(s):
            curr = start + 1
            while curr < len(s) and s[start] == s[curr]:
                curr += 1
            result.extend((str(curr - start), s[start]))
            start = curr
        return "".join(result)


if __name__ == "__main__":
    assert Solution().countAndSay(4) == "1211"
    assert Solution().countAndSay(5) == "111221"

歡迎查看我的Github來獲得相關源碼。