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

মান লিজিয়ে আমাদের দুটি স্ট্রিং s এবং t আছে শুধু তিনটি ক্যারেক্টারের সাথে: 'A', 'B' এবং '#'। আমাদের যাচাই করতে হবে s-কে t-তে রূপান্তর করা সম্ভব কিনা নিচের অপারেশনগুলো করে:

• 'A' শুধু বাম দিকে (left hand side) যেতে পারে
• 'B' শুধু ডান দিকে (right hand side) যেতে পারে
• 'A' এবং 'B' কেউ একে অপরে ক্রস (cross) করতে পারবে না

যেমন, ইনপুট যদি s = "##AB##B", t = "A###B#B" হয়, তবে আউটপুট হবে True কারণ s-এ 'A' সহজে বামপাশে যেতে পারে, এবং মাঝপথের 'B' এক ধাপ ডানে যেতে পারে।

সমাধানের ধাপসমূহ

• s := s-এর ক্যারেক্টারগুলো নিয়ে একটি লিস্ট
• t := t-এর ক্যারেক্টারগুলো নিয়ে একটি লিস্ট
• যদি s-এর সাইজ t-এর সাইজ সমান না হয়, তবে:
  • False রিটার্ন করুন
• যদি s এবং t-এ 'A'-এর কাউন্ট ভিন্ন হয় অথবা 'B'-এর কাউন্ট ভিন্ন হয়, তবে:
  • False রিটার্ন করুন
• i ০ থেকে s-এর সাইজ - ১ পর্যন্ত, করুন:
  • যদি s[i] '#' নয়, তবে:
    • j ০ থেকে t-এর সাইজ - ১ পর্যন্ত, করুন:
      • যদি (t[j] != s[i]) এবং t[j] != '#' হয়, তবে:
        • False রিটার্ন করুন
      • যদি t[j] == s[i] হয়, তবে:
        • t[j] := '#'
        • যদি s[i] == 'A' এবং i < j হয়, তবে:
          • False রিটার্ন করুন
        • যদি s[i] == 'B' এবং i > j হয়, তবে:
          • False রিটার্ন করুন
        • লুপ থেকে বের হোন
• True রিটার্ন করুন

উদাহরণ

বेहतर বোঝার জন্য নিচের বাস্তবায়নটি দেখুন:

def solve(s, t):
    s = list(s)
    t = list(t)
    if len(s) != len(t):
        return False
    if s.count('A') != t.count('A') or s.count('B') != t.count('B'):
        return False
    for i in range(len(s)):
        if s[i] != '#':
            for j in range(len(t)):
                if (t[j] != s[i]) and t[j] != '#':
                    return False
                if t[j] == s[i]:
                    t[j] = '#'
                    if s[i] == 'A' and i < j:
                        return False
                    if s[i] == 'B' and i > j:
                        return False
                    break
    return True

s = "##AB##B"
t = "A###B#B"
print(solve(s, t))

ইনপুট

"##AB##B", "A###B#B"

আউটপুট

True