ধরুন আমাদের দুটি স্ট্রিং আছে ছোট হাতের স্ট্রিং 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 দ্বারা কমিয়ে দিন
- অন্যথায়,
- মিথ্যে ফেরত দিন
- যদি freq[t[i]] অ-শূন্য হয়, তাহলে
- সত্য ফেরান
আরো ভালোভাবে বোঝার জন্য আসুন নিচের বাস্তবায়ন দেখি -
উদাহরণ
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