โปรแกรมตรวจสอบการแบ่ง String เป็นค่าต่อเนื่องลดลงใน Python

ปัญหา

สตริง s ตัวเลข בלבד แบ่งเป็น Substrings ≥ 2 ชิ้น ให้ค่าตัวเลขเป็น Non-increasing และต่างกันทีละ 1 ตรวจสอบว่าเป็นไปได้หรือไม่

ตัวอย่าง

s = "080076" → True

Split: ["08", "007", "6"] → Values: [8, 7, 6] ✓

อัลกอริทึม (DFS + Backtracking)

1. DFS(index, prev_value): ลองตัด Substring เริ่มจาก Index
2. ถ้า Substring ที่เหลือ = prev - 1 → Success
3. ลองความยาว Substring 1 ถึง n-idx-1
4. แปลงเป็น Int, ตรวจสอบเงื่อนไข, Recurse
5. Base Case: Index == n และ Valid

ตัวอย่างโค้ด

def dfs(s, pre, idx, n):
    if pre != -1 and int(s[idx:]) == pre - 1:
        return True
    for i in range(1, n - idx):
        curs = s[idx:idx+i]
        cur = int(curs)
        if pre == -1:
            if dfs(s, cur, idx + i, n):
                return True
        else:
            if cur == pre - 1 and dfs(s, cur, idx + i, n):
                return True
    return False

def solve(s):
    n = len(s)
    if n <= 1:
        return False
    return dfs(s, -1, 0, n)

s = "080076"
print(solve(s))  # True

ความซับซ้อน

• Time: O(2^n) Worst Case (Exponential - ทุกจุดตัดลอง/ไม่ลอง)
• Space: O(n) Recursion Depth
• Optimization: Memoization (idx, prev) หรือ Greedy Check