38. Count and Say

Approach 1: Brute Force

Since there is a limit to what n can be, evaluating it will using brute force will still be safe and will not Time out

class Solution:
    def countAndSay(self, n):
        """        
        :type n: int
        :rtype: str
        """
        ans = ['1']
        for i in range(n):
            prev = '0'
            count = 0
            s = ''
            for j in ans[i]:
                if prev == '0': 
                    prev = j
                    count = 1
                elif j != prev:
                    s += str(count)
                    s += prev
                    count = 1
                    prev = j
                else:
                    count += 1
            if count or prev:
                s += str(count)
                s += prev
                count = 1
                prev = j
            ans.append(s)
        return ans[n-1]

Now that we are successfully able to find out the answer, we can easily just use our list ans and just return the required index number. Moreover since the range is of n is under 30, we can be sure that the memory won't be too much of a strain either. That is what I have adopted in Approach 2 as well

Time Complexity: O(n)

Space Complexity: O(n)

Approach 2: Stored Brute Force

Time Complexity: O(1)

Space Complexity: O(n) or O(1) (since the upper bound for n is given)

Previous17. Letter Combinations of a Phone NumberNext521. Longest Uncommon Subsequence I

Last updated