Giả sử chúng ta có một chuỗi s chỉ có các số. Chúng ta phải kiểm tra xem liệu chúng ta có thể chia s thành hai hoặc nhiều chuỗi con không rỗng sao cho các giá trị số của các chuỗi con đó theo thứ tự không tăng và sự khác biệt giữa các giá trị số của mỗi hai chuỗi con liền kề là 1. Vì vậy, ví dụ, nếu chuỗi là s ="0080079" chúng ta có thể chia nó thành ["0080", "079"] với các giá trị số [80, 79]. Và các giá trị theo thứ tự giảm dần và các giá trị liền kề chênh lệch nhau 1, vì vậy cách này là hợp lệ. Chúng tôi phải kiểm tra xem liệu có thể tách các s như đã mô tả ở trên hay không.
Vì vậy, nếu đầu vào là s ="080076", thì đầu ra sẽ là True vì chúng ta có thể chia nó như ["08", "007", "6"], vì vậy giá trị số là [8,7,6] .
Để giải quyết vấn đề này, chúng tôi sẽ làm theo các bước sau -
-
Định nghĩa một hàm dfs (). Điều này sẽ lấy s, pre, idx, n
-
nếu pre không phải là -1 và dạng số nguyên của (chuỗi con của s [từ chỉ mục idx đến end]) giống với trước -1 thì
-
trả về True
-
-
đối với tôi trong phạm vi từ 1 đến n-idx-1, hãy thực hiện
-
rủa:=chuỗi con của s [từ idx chỉ mục đến idx + i-1]
-
cur:=curs as number
-
nếu trước giống -1, thì
-
nếu dfs (s, cur, idx + i, n) là true thì
-
trả về True
-
-
nếu không,
-
nếu cur giống với pre-1 và dfs (s, cur, idx + i, n) là true thì
-
trả về True
-
-
-
-
-
trả về Sai
-
Từ phương thức chính, hãy thực hiện như sau
-
n:=kích thước của s
-
nếu n <=1, thì
-
trả về Sai
-
-
trả về dfs (s, -1, 0, n)
Ví dụ
Hãy cùng chúng tôi xem cách triển khai sau để hiểu rõ hơn -
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))
Đầu vào
"080076"
Đầu ra
True