Simple Python Solution


  • 16
    S

    Idea here is keep track of the first letter in the sequence and count consecutive occurances. Once you encounter a new letter you add the previous count and letter to the chain. Repeat n-1 times (since we seeded the initial '1' case). We always update temp after the inner loop since we will never have already added the last sequence.

         def countAndSay(self, n):
            s = '1'
            for _ in range(n-1):
                let, temp, count = s[0], '', 0
                for l in s:
                    if let == l:
                        count += 1
                    else:
                        temp += str(count)+let
                        let = l
                        count = 1
                temp += str(count)+let
                s = temp
            return s

  • 0
    L

    what's the time complexity of the algorithm? O(2^n) ?


  • 8
    S

    In Python its more efficient to use ''.join() to concatenate strings. So it will be faster to use a list to store the substrings and join them at the end.

    class Solution(object):
        def countAndSay(self, n):
            """
            :type n: int
            :rtype: str
            """
            s = '1'
            for i in range(n-1):
                count = 1
                temp = []
                for index in range(1, len(s)):
                    if s[index] == s[index-1]:
                        count += 1
                    else:
                        temp.append(str(count))
                        temp.append(s[index-1])
                        count = 1
                temp.append(str(count))
                temp.append(s[-1])
                s = ''.join(temp)
            return s
    

  • 0
    B

    same method with recursive implementation in Python.

    class Solution(object):
        def countAndSay(self, n):
            if n == 1: return "1"
            s = self.countAndSay(n-1)
            i, ch, tmp = 0, s[0], ''
            for j in range(1, len(s)):
                if s[j] != ch:
                    tmp += str(j-i) + ch
                    i, ch = j, s[j]
            tmp += str(len(s)-i) + ch
            return tmp
    

  • 0
    H

    '''class Solution(object):
    def countAndSay(self, n):
    arr = [1]
    for i in range(n-1):

            temp = []
            count = 1 
            for i,x in enumerate(arr[1:],1):
                if arr[i-1] == x:
                    count += 1
                else:
                    temp.append(count)
                    temp.append(arr[i-1])
                    count = 1 
            temp.append(count)
            temp.append(arr[i])
                
            arr = temp
        return "".join(map(str,arr))
    

    '''


Log in to reply
 

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