資料結構
網路
關係資料庫管理系統 (RDBMS)
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C語言程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理學
化學
生物學
數學
英語
經濟學
心理學
社會學
服裝設計
法學Python程式：檢查字串是否可以拆分為遞減的連續值
假設我們有一個只包含數字的字串s。我們必須檢查是否可以將s拆分為兩個或多個非空子字串，使得這些子字串的數值構成一個非遞增序列，並且每兩個相鄰子字串的數值差為1。例如，如果字串是s = "0080079"，我們可以將其拆分為["0080", "079"]，數值為[80, 79]。這些值按降序排列，相鄰值相差1，因此這種方式有效。我們必須檢查是否可以按上述方式拆分s。
因此，如果輸入類似於s = "080076"，則輸出將為True，因為我們可以將其拆分為["08", "007", "6"]，因此數值為[8,7,6]。
為了解決這個問題，我們將遵循以下步驟：
定義一個函式dfs()。它將接收s、pre、idx、n。
如果pre不為-1，並且s[從索引idx到末尾]的整數形式等於pre -1，則
返回True
對於i從1到n-idx-1，執行：
curs := s[從索引idx到idx+i-1]的子字串
cur := curs作為數字
如果pre等於-1，則
如果dfs(s, cur, idx+i, n)為真，則
返回True
否則，
如果cur等於pre - 1並且dfs(s, cur, idx+i, n)為真，則
返回True
返回False
在主方法中，執行以下操作：
n := s的大小
如果n <= 1，則
返回False
返回dfs(s, -1, 0, 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))
輸入
"080076"
輸出
True
更新於：2021年10月8日
199 次瀏覽
廣告