Simple Python Solution

• 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``````

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

• 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
``````

• 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
``````

• '''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))
``````

'''

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