Chương trình kiểm tra chuỗi có chứa dãy số giảm dần liên tiếp không trong Python

Cho chuỗi chữ số s, kiểm tra xem có thể tách thành dãy số giảm dần liên tiếp (ví dụ 99,98,97,96) không.

Ví dụ

Đầu vào: "99989796".
Đầu ra: True.

Thuật toán

1. Đệ quy thử tất cả độ dài số đầu tiên (tối đa n//2).
2. Hàm helper(pos, prev_num): nếu pos == n trả về True. Thử lấy 1 hoặc 2 chữ số tiếp theo (theo độ dài của prev_num) xem có bằng prev_num-1 không, nếu có thì đệ quy.

Mã nguồn Python

class Solution:
    def solve(self, s):
        n = len(s)
        def helper(pos, prev_num):
            if pos == n:
                return True
            num_digits = len(str(prev_num))
            for i in range(num_digits - 1, num_digits + 1):
                if s[pos:pos+i] and int(s[pos:pos+i]) == prev_num - 1:
                    if helper(pos + i, prev_num - 1):
                        return True
            return False
        for i in range(1, n//2 + 1):
            num = int(s[:i])
            if helper(i, num):
                return True
        return False

ob = Solution()
s = "99989796"
print(ob.solve(s))

Đầu vào / Đầu ra

Input: "99989796"
Output: True