count_and_say.py

# -*- coding: utf-8 -*-

class Solution:
    # @param {int} n the nth
    # @return {string} the nth sequence
    def countAndSay(self, n):
        # Write your code here
        return self._countAndSay(n)

    def _countAndSay(self, n):
        if n == 1:
            return '1'
        ret = ''
        prev_str = self._countAndSay(n - 1)
        i = 0
        while i < len(prev_str):
            ch = prev_str[i]
            sum = 1
            j = i + 1
            while j < len(prev_str):
                if prev_str[i] == prev_str[j]:
                    sum += 1
                    j += 1
                else:
                    break
            ret += str(sum)
            ret += ch
            i = j
        return ret