जांचें कि क्या पायथन में दिए गए बाधाओं का उपयोग करके किसी अन्य स्ट्रिंग से एक स्ट्रिंग बनाई जा सकती है

मान लीजिए कि हमारे पास दो स्ट्रिंग्स लोअरकेस स्ट्रिंग्स s और t हैं। हमें यह जांचना होगा कि निम्नलिखित बाधाओं का उपयोग करके s से t उत्पन्न किया जा सकता है या नहीं -

• उदाहरण के लिए t के वर्ण s में हैं यदि t में दो 'a' हैं, तो s में भी दो 'a' होने चाहिए।

• जब t में कोई वर्ण s में नहीं है, तो जाँच करें कि पिछले दो वर्ण (पिछले दो ASCII मान) s में हैं या नहीं। उदाहरण के लिए, यदि 'f' t में है लेकिन s में नहीं है, तो 'f' बनाने के लिए s से 'd' और 'e' का उपयोग किया जा सकता है।

इसलिए, यदि इनपुट s ="pghn" t ="pin" जैसा है, तो आउटपुट सही होगा क्योंकि हम 'g' से 'i' बना सकते हैं और 'h' को "pin" बना सकते हैं।

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

• आवृत्ति:=s में प्रत्येक वर्ण की आवृत्ति
• i के लिए 0 से t के आकार की सीमा में, करें
  • अगर freq[t[i]] शून्य नहीं है, तो
    • freq[t[i]] :=freq[t[i]] - 1
  • अन्यथा जब freq[t[i]] का पहला पिछला वर्ण और freq[t[i] का दूसरा पिछला वर्ण शून्य नहीं है, तब
    • फ़्रीक को कम करें[t का पहला पिछला वर्ण[i]] 1 से कम करें
    • फ़्रीक घटाएं[t[i]] का दूसरा पिछला वर्ण 1
  • अन्यथा,
    • झूठी वापसी
• सही लौटें

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

उदाहरण

from collections import defaultdict
def solve(s, t):
   freq = defaultdict(lambda:0)
   for i in range(0, len(s)):
      freq[s[i]] += 1
   for i in range(0, len(t)):
      if freq[t[i]]:
         freq[t[i]] -= 1
      elif (freq[chr(ord(t[i]) - 1)] and freq[chr(ord(t[i]) - 2)]):
         freq[chr(ord(t[i]) - 1)] -= 1
         freq[chr(ord(t[i]) - 2)] -= 1
      else:
         return False
   return True
s = "pghn"
t = "pin"
print(solve(s, t))

इनपुट

"pghn", "pin"

आउटपुट

True