पायथन में जांचें कि स्ट्रिंग उपस्ट्रिंग सॉर्ट संचालन से परिवर्तनीय है या नहीं

मान लीजिए हमारे पास दो संख्यात्मक स्ट्रिंग्स s और t हैं, हम निम्न संचालन का उपयोग करके किसी भी संख्या में स्ट्रिंग s को t में बदलना चाहते हैं: 1. s में एक गैर-खाली उपस्ट्रिंग चुनें और उसे स्थानांतरित क्रम में सॉर्ट करें ताकि वर्ण आरोही क्रम में हों। हमें जांचना है कि क्या स्ट्रिंग s को स्ट्रिंग t में बदलना संभव है या नहीं।

इसलिए, यदि इनपुट है s = "95643" t = "45963", तो आउटपुट True होगा क्योंकि हम s को t में इस तरह बदल सकते हैं: "95643" → "95463" → "45963"।

इसे हल करने के लिए, हम निम्न चरणों का पालन करेंगे:

• places := एक मैप जहां डिफ़ॉल्ट मान प्रकार सूची है

• i को s के आकार से 0 तक नीचे के लिए, करें

  • key := s[i] को पूर्णांक के रूप में

  • i को places[key] के अंत में डालें

• t में प्रत्येक e के लिए, करें

  • key := e को पूर्णांक के रूप में

    • यदि places[key] खाली है, तो

      • False वापस करें

    • i := places[key] का अंतिम तत्व

    • j को 0 से key - 1 तक के लिए, करें

      • यदि places[j] शून्येतर है और places[j] का अंतिम तत्व < i, तो

        • False वापस करें

    • places[key] से अंतिम तत्व हटाएं

• True वापस करें

उदाहरण

बेहतर समझ के लिए निम्न कार्यान्वयन देखें:

from collections import defaultdict

def solve(s, t):
    places = defaultdict(list)
    for i in reversed(range(len(s))):
        key = int(s[i])
        places[key].append(i)
    for e in t:
        key = int(e)
        if not places[key]:
            return False
        i = places[key][-1]
        for j in range(key):
            if places[j] and places[j][-1] < i:
                return False
        places[key].pop()
    return True

s = "95643"
t = "45963"
print(solve(s, t))

इनपुट

"95643", "45963"

आउटपुट

True