Chương trình tìm số hạng thứ n trong dãy Look and Say trong Python

Mô tả bài toán

Cho số n, tạo số hạng thứ n của dãy "Look and Say". Dãy bắt đầu bằng "1", mỗi số hạng sau được đọc từ số hạng trước: đếm số lượng ký tự liên tiếp giống nhau.

Các số hạng đầu: 1, 11, 21, 1211, 111221, ...

Ví dụ: n = 5 → đầu ra "111221".

Giải thuật (Mô phỏng)

1. Khởi tạo s = "1".
2. Nếu n == 1 trả về s.
3. Lặp từ 2 đến n:
   • Duyệt qua chuỗi s, đếm các ký tự liên tiếp giống nhau.
   • Xây dựng chuỗi mới temp bằng cách nối count và char.
   • Gán s = temp.
4. Trả về s.

Ví dụ mã Python

class Solution(object):
    def solve(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

ob = Solution()
n = 5
print(ob.solve(n))

Đầu vào

5

Đầu ra

"111221"