Python solution but what is the runtime?


  • 0
    F

    seems in every step, the string grows in an inconsistent size? for the helper function itself takes O(S) time but when it starts to recurse, I do not know how to calculate the Big O

    def countAndSayHelper(s, n):
        if n == 1:
            return s
    
        seq = ''
        cnt = 0
        f = s[0]
        for i in range(len(s)):
            if s[i] == f:
                cnt += 1
            else:
                seq += str(cnt) + f
                cnt = 1
                f = s[i]
    
        seq += str(cnt) + f
        return countAndSayHelper(seq, n - 1)
    

Log in to reply
 

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