Simple Python solution using recursion


  • 0
    R

    The main idea is build the sequence from 1st to nth term recursively. O(n^2) time complexity O(1) space complexity.

     class Solution(object):
            def countAndSay(self, n):
                numStr = '1'
                for _ in range(n - 1):
                    numStr = self.numConvert(numStr)
                return numStr
        
            def numConvert(self, numStr):
                ans = ''
                count = 1
                for i in range(len(numStr)):
                    if i == len(numStr) - 1:
                        ans += str(count) + numStr[i]
                    elif numStr[i] == numStr[i + 1]:
                        count += 1
                    else:
                        ans += str(count) + numStr[i]
                        count = 1
                return ans

  • 1
    A

    @ray24 This is not recursion. You are not calling the function inside the same function. Instead you are calling the function in series using for loop.

    Could you explain how did you determine the run time as O(N^2) ?


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.