Đếm và nói (Count and Say) trong Python

Dãy Count-and-Say: 1, 11, 21, 1211, 111221,... Mỗi hàng đọc hàng trước. Cho n (1≤n≤30), tạo hàng thứ n.

Giải pháp

Xây dựng lặp:

• s = "1". Nếu n=1 trả về s.
• Lặp i=2..n: duyệt s, đếm ký tự liên tiếp, xây temp = count+char.
• Cập nhật s = temp.

Ví dụ

Triển khai Python:

class Solution(object): 
    def countAndSay(self, n): 
        s = "1" 
        if n == 1: 
            return s 
        for i in range(2,n+1): 
            j = 0 
            temp = "" 
            curr = "" 
            count = 0 
            while j<len(s): 
                if curr =="": 
                    curr=s[j] 
                    count=1 
                    j+=1 
                elif curr == s[j]: 
                    count+=1 
                    j+=1 
                else: 
                    temp+= str(count) + curr 
                    curr="" 
                    count = 0 
            temp+=str(count) + curr 
            s=temp 
        return s 
ob1 = Solution() 
print(ob1.countAndSay(6))

Đầu vào

print(ob1.countAndSay(6))

Đầu ra

312211