পাইথনে সাবস্ট্রিং সর্ট অপারেশন দিয়ে স্ট্রিং ট্রান্সফর্ম করা সম্ভব কিনা চেক করার প্রোগ্রাম

মনে করুন s এবং t নামক দুটি Нуমেরিক স্ট্রিং আছে। আমরা s থেকে t-এ নিচের অপারেশন যেকোনো সংখ্যক বার প্রয়োগ করে ট্রান্সফর্ম করতে চাই: ১. s-এ একটি নন-এম্পটি সাবস্ট্রিং সিলেক্ট করুন এবং সেটাকে ইনপ্লেস সর্ট করুন যাতে ক্যারেক্টারগুলো অ্যাসেন্ডিং অর্ডারে থাকে। স্ট্রিং s কে t-এ ট্রান্সফর্ম করা সম্ভব কিনা চেক করতে হবে।

যেমন, ইনপুট s = "95643", t = "45963" হলে, আউটপুট হবে True কারণ "95643" → "95463" → "45963" এভাবে ট্রান্সফর্ম করা যায়।

সমাধান পদ্ধতি

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

• places := ডিফল্ট ভ্যালু টাইপ লিস্ট olan একটি ম্যাপ

• i = s-এর সাইজ - ১ থেকে ০ পর্যন্ত (উল্টো ক্রমে)

  • key := s[i] ইন্টিজার আকারে

  • i কে places[key]-এর শেষে অ্যাপেন্ড করুন

• t-এ থাকা প্রতিটি e-এর জন্য

  • key := e ইন্টিজার আকারে

    • যদি places[key] খালি থাকে, তবে

      • False রিটার্ন করুন

    • i := places[key]-এর শেষ এলিমেন্ট

    • j = 0 থেকে key - ১ পর্যন্ত

      • যদি places[j] নন-এম্পটি এবং places[j]-এর শেষ এলিমেন্ট < i হয়, তবে

        • False রিটার্ন করুন

    • places[key]-এর শেষ এলিমেন্ট ডিলিট করুন

• True রিটার্ন করুন

উদাহরণ

নিচের ইমপ্লিমেন্টেশনটি দেখুন আরও ভালো বোঝার জন্য:

from collections import defaultdict def solve(s, t): places = defaultdict(list) for i in reversed(range(len(s))): key = int(s[i]) places[key].append(i) for e in t: key = int(e) if not places[key]: return False i = places[key][-1] for j in range(key): if places[j] and places[j][-1] < i: return False places[key].pop() return True s = "95643" t = "45963" print(solve(s, t))

ইনপুট

"95643", "45963" 

আউটপুট

True