मान लीजिए कि हमारे पास केवल संख्याओं के साथ एक स्ट्रिंग है। हमें यह जांचना होगा कि क्या हम s को दो या दो से अधिक गैर-रिक्त सबस्ट्रिंग में विभाजित कर सकते हैं जैसे कि उन सबस्ट्रिंग के संख्यात्मक मान गैर-बढ़ते क्रम में हैं और प्रत्येक दो आसन्न सबस्ट्रिंग के संख्यात्मक मानों के बीच का अंतर 1 है। तो उदाहरण के लिए, यदि स्ट्रिंग s ="0080079" है, हम इसे ["0080", "079"] में संख्यात्मक मानों [80, 79] के साथ विभाजित कर सकते हैं। और मान अवरोही क्रम में हैं और आसन्न मान 1 से भिन्न हैं, इसलिए यह तरीका मान्य है। हमें यह जांचना होगा कि ऊपर वर्णित अनुसार s को विभाजित करना संभव है या नहीं।
इसलिए, यदि इनपुट s ="080076" जैसा है, तो आउटपुट सही होगा क्योंकि हम इसे ["08", "007", "6"] की तरह विभाजित कर सकते हैं, इसलिए संख्यात्मक मान [8,7,6] हैं। ।
इसे हल करने के लिए, हम इन चरणों का पालन करेंगे -
-
फ़ंक्शन को परिभाषित करें dfs() । इसमें s, pre, idx, n
. लगेगा -
यदि प्री -1 नहीं है और (एस [इंडेक्स आईडीएक्स से अंत तक] का सबस्ट्रिंग) का पूर्णांक रूप प्री -1 के समान है, तो
-
सही लौटें
-
-
1 से n-idx-1 की श्रेणी में i के लिए, करें
-
शाप :=s का सबस्ट्रिंग [इंडेक्स idx से idx+i-1]
-
वक्र:=संख्या के रूप में शाप
-
अगर प्री -1 के समान है, तो
-
अगर dfs(s, cur, idx+i, n) सही है, तो
-
सही लौटें
-
-
अन्यथा,
-
यदि cur पूर्व -1 के समान है और dfs(s, cur, idx+i, n) सत्य है, तो
-
सही लौटें
-
-
-
-
-
झूठी वापसी
-
मुख्य विधि से, निम्न कार्य करें
-
n :=s का आकार
-
अगर n <=1, तो
-
झूठी वापसी
-
-
वापसी 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