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

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

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

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

समाधान दृष्टिकोण

हम s में प्रत्येक वर्ण की आवृत्ति गिनते हैं। फिर t के प्रत्येक वर्ण के लिए, हम पहले सीधे मिलान की कोशिश करते हैं। यदि नहीं मिलता, तो पिछले दो ASCII वर्णों की जांच करते हैं।

एल्गोरिदम चरण:

1. s में प्रत्येक वर्ण की आवृत्ति freq में गिनें
2. t के प्रत्येक वर्ण t[i] के लिए:
• यदि freq[t[i]] > 0, तो घटाएं
• अन्यथा यदि freq[chr(ord(t[i])-1)] > 0 और freq[chr(ord(t[i])-2)] > 0:
• दोनों पिछले वर्णों की आवृत्ति 1-1 से घटाएं
• अन्यथा False लौटाएं
3. True लौटाएं

पायथन कार्यान्वयन

from collections import defaultdict

def solve(s, t):
    freq = defaultdict(int)
    for ch in s:
        freq[ch] += 1
    
    for ch in t:
        if freq[ch] > 0:
            freq[ch] -= 1
        elif freq[chr(ord(ch) - 1)] > 0 and freq[chr(ord(ch) - 2)] > 0:
            freq[chr(ord(ch) - 1)] -= 1
            freq[chr(ord(ch) - 2)] -= 1
        else:
            return False
    return True

s = "pghn"
t = "pin"
print(solve(s, t))  # True

इनपुट

"pghn", "pin"

आउटपुट

True

व्याख्या:

s = "pghn" → आवृत्तियां: p=1, g=1, h=1, n=1

t = "pin":

• 'p': s में मौजूद है → freq['p'] = 0
• 'i': s में नहीं है। पिछले दो: 'h' (104) और 'g' (103)। दोनों मौजूद हैं → freq['h']=0, freq['g']=0
• 'n': s में मौजूद है → freq['n'] = 0

सभी वर्ण मिल गए!