Python में एक स्ट्रिंग को दूसरी स्ट्रिंग में बदलने की संभावना की जांच कैसे करें?

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

• कुछ लोअरकेस अक्षरों को अपरकेस में बदलें।
• सभी लोअरकेस अक्षरों को हटा दें।

तो, यदि इनपुट s = "fanToM", t = "TOM" है, तो आउटपुट True होगा क्योंकि हम 'o' को 'O' में बदल सकते हैं फिर s से अन्य सभी लोअरकेस अक्षरों को हटाकर इसे t बना सकते हैं।

हल करने के चरण

• n := s का आकार, m := t का आकार
• dp:= आकार (m + 1)x(n + 1) का मैट्रिक्स और False से भरें
• dp[0, 0] := True
• रेंज 0 से s के आकार - 1 तक के लिए i, करें:
  • रेंज 0 से t के आकार तक के लिए j, करें:
    • यदि dp[i, j] True है, तो:
      • यदि j < t का आकार और s[i] का अपरकेस t[j] के समान है, तो:
        • dp[i + 1, j + 1] := True
      • यदि s[i] अपरकेस में नहीं है, तो:
        • dp[i + 1, j] := True
• dp[n, m] लौटाएं

उदाहरण

def solve(s,t):
    n = len(s)
    m = len(t)
    dp= [[False for i in range(m+1)] for i in range(n+1)]
    dp[0][0] = True
    for i in range(len(s)):
        for j in range(len(t)+1):
            if dp[i][j] == True:
                if j < len(t) and (s[i].upper() == t[j]):
                    dp[i + 1][j + 1] = True
                if s[i].isupper()==False:
                    dp[i + 1][j] = True
    return dp[n][m]

s = "fanToM"
t = "TOM"
print(solve(s, t))

इनपुट

"fanToM", "TOM"

आउटपुट

True