Leetcode 38. Count and Say

https://leetcode.com/problems/count-and-say/

The simple way to solve is to perform n-1 transitions. The way of transition is, as the title stated, count and say.

Solution:

# T:O(n*2^n) S:O(2^n)
class Solution:
    # @param {integer} n
    # @return {string}
    def perform(self, A):  #perform change on A and return it
        i, B = 0, []
        while i < len(A):
            count = 1
            while i < len(A) - 1 and A[i] == A[i + 1]:
                i += 1
                count += 1
            B.append(str(count)+A[i])
            i += 1
        return ''.join(B)
        
    def countAndSay(self, n):
        str = '1'
        if n == 1:
            return str
        for i in xrange(n-1):
            str = self.perform(str)
        return str

Run Time: 56 ms