38. Count-And-Say

Recursive brute force-esque algorithm. Its nice to have another helper function called encode that can encode the current string to its RLE form. Then we can recurse through the n with n == 1 being the base case returning a string of "1". We repeatedly encode the output using RLE and return once we do it n times.

class Solution(object):
    def countAndSay(self, n):
        """
        :type n: int
        :rtype: str
        """
        if n == 1:
            return "1"

        return self.encode(self.countAndSay(n - 1))

    def encode(self, x):
        count = 1
        curr = x[0]
        res = ""
        for i in range(1, len(x)):
            if x[i] == curr:
                count += 1
            else:
                res += str(count) + str(curr)
                count = 1
                curr = x[i]

        res += str(count) + str(curr)

        return res

Time Complexity: O(2^n)

Space Complexity: O(2^n)

Time Taken: forgot to keep track