Cho chuỗi s chỉ chứa chữ số. Kiểm tra có thể tách s thành ≥2 substring không rỗng sao cho giá trị số của chúng giảm dần liên tiếp (chênh lệch 1). Ví dụ: "0080079" → [80,79] hợp lệ.
Ví dụ: s = "080076" → True (tách [08, 007, 6] → [8,7,6]).
Giải thuật (DFS backtracking)
- DFS(s, pre, idx, n): pre = giá trị chunk trước, idx = vị trí hiện tại.
- Nếu phần còn lại int(s[idx:]) == pre-1 → True.
- Thử mọi độ dài chunk tiếp theo từ idx: curs = s[idx:idx+i], cur = int(curs).
- Nếu pre == -1 (chunk đầu) hoặc cur == pre-1 → đệ quy DFS(s, cur, idx+i, n).
- Nếu tìm thấy → True, else False.
Code Python
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
Đầu vào / Đầu ra
Input: "080076"
Output: True