পাইথনে প্রদত্ত সীমাবদ্ধতা ব্যবহার করে অন্য স্ট্রিং থেকে একটি স্ট্রিং তৈরি করা যায় কিনা তা পরীক্ষা করুন

ধরুন আমাদের দুটি স্ট্রিং আছে ছোট হাতের স্ট্রিং 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" এর মত হয়, তাহলে আউটপুটটি True হবে কারণ আমরা 'g' থেকে 'i' এবং 'পিন' তৈরি করতে 'h' করতে পারি।

এটি সমাধান করতে, আমরা এই পদক্ষেপগুলি অনুসরণ করব -

• freq :=s এ প্রতিটি অক্ষরের ফ্রিকোয়েন্সি
• আমি 0 থেকে t আকারের রেঞ্জের জন্য,
  করুন
  • যদি freq[t[i]] অ-শূন্য হয়, তাহলে
    • freq[t[i]] :=freq[t[i]] - 1
  • অন্যথায় যখন freq[t[i]] এর প্রথম পূর্ববর্তী অক্ষর এবং freq[t[i]] এর দ্বিতীয় পূর্ববর্তী অক্ষর অ-শূন্য হয়, তখন
    • freq[t[i] এর প্রথম পূর্ববর্তী অক্ষর] 1 কমিয়ে দিন
    • freq[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