পাইথনে একটি স্ট্রিংকে অন্য স্ট্রিংে রূপান্তর করা সম্ভব কিনা যাচাই করার পদ্ধতি

মান লেও আমাদের দুটি স্ট্রিং s এবং t আছে, যেখানে t বড় হাতের অক্ষরে (uppercase) লেখা। আমাদের যাচাই করতে হবে কি আমরা s-কে t-তে রূপান্তর করতে পারি নিচের অপারেশনগুলো انجام দিয়ে:

• কিছু ছোট হাতের অক্ষর (lowercase letters) বড় হাতের অক্ষরে (uppercase) রূপান্তর করা।
• সभी ছোট হাতের অক্ষর মুছে ফেলা।

তাই, যদি ইনপুট হয় s = "fanToM", t = "TOM", তবে আউটপুট হবে True কারণ আমরা 'o'-কে 'O'-তে পরিবর্তন করে s-থেকে সব ছোট হাতের অক্ষর মুছে t বানাতে পারি।

এটি সমাধান করার জন্য আমরা নিচের ধাপগুলো অনুসরণ করব:

• n := s-এর সাইজ, m := t-এর সাইজ
• dp := (m + 1) x (n + 1) আকারের একটি ম্যাট্রিক্স যা False দিয়ে ভরা
• dp[0, 0] := True
• i = 0 থেকে s-এর সাইজ - 1 পর্যন্ত, করুন
  • j = 0 থেকে t-এর সাইজ পর্যন্ত, করুন
    • যদি 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