पायथन में जांचें कि क्या स्ट्रिंग को अवरोही क्रमागत मानों में विभाजित किया जा सकता है

मान लीजिए हमारे पास केवल संख्याओं वाली एक स्ट्रिंग 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