Python দিয়ে K মুভে স্ট্রিং কনভার্ট করা সম্ভব কিনা চেক করার প্রোগ্রাম

মান লাগিয়ে, আমাদের দুটি স্ট্রিং s এবং t আছে, আমাদের চেক করতে হবে s কি t-তে k মুভ বা কমে কনভার্ট করা যায়। i-তম মুভে আপনি এই অপারেশনগুলো করতে পারেন:

• s-এ যেকোনো ইন্ডেক্স j (১ থেকে শুরু) সিলেক্ট করুন যাতে 1 <= j <= s-এর আকার এবং j কোনো আগের মুভে সিলেক্ট করা নয়, এবং সেই ইন্ডেক্সের ক্যারেক্টার i বার শিফট করুন।
• যেনে রাখুন।

এখানে শিফট মানে ক্যারেক্টারকে অ্যালফাবেটের পরবর্তী লেটার দিয়ে রিপ্লেস করা (যদি লেটার 'z' হয়, তবে 'a'-তে র‍্যাপ করুন)। এক ক্যারেক্টার i বার শিফট করা মানে শিফট অপারেশন i বার প্রয়োগ করা।

যেমন, ইনপুট s = "poput", t = "vwput", k = 9 হলে, আউটপুট হবে True কারণ i = 6-তে 'p' কে 'v' বানানো যায়, এবং i = 8-তে 'o' কে 'w' বানানো যায়।

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

• যদি s এবং t-এর আকার সমান না হয়, তবে False রিটার্ন করুন
• count := একটি অ্যারে যা (min(1, k - i + 1) + (k - i)//26) ধারণ করে i = 0 থেকে 25 পর্যন্ত
• s-এর প্রতিটি c1 এবং t-এর c2 জন্য:
  • যদি c1 != c2 হয়, তবে:
    • diff := (ord(c2) - ord(c1) + 26) % 26
    • যদি count[diff] <= 0 হয়, তবে False রিটার্ন করুন
    • count[diff] := count[diff] - 1
• True রিটার্ন করুন

বेहतर বোঝার জন্য নিচের ইমপ্লিমেন্টেশন দেখুন:

উদাহরণ

def solve(s, t, k):
    if len(s) != len(t):
        return False
    count = [min(1, k - i + 1) + (k - i)//26 for i in range(26)]
    for c1, c2 in zip(s, t):
        if (c1 != c2):
            diff = (ord(c2) - ord(c1) + 26) % 26
            if count[diff] <= 0:
                return False
            count[diff] -= 1
    return True
s = "poput"
t = "vwput"
k = 9
print(solve(s, t,k))

ইনপুট

"poput","vwput",9

আউটপুট

True