পাইথনে সাবস্ট্রিং সর্ট অপারেশনের মাধ্যমে স্ট্রিং রুপান্তরযোগ্য কিনা তা পরীক্ষা করার জন্য প্রোগ্রাম

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

সুতরাং, যদি ইনপুটটি s ="95643" t ="45963" এর মতো হয়, তবে আউটপুটটি True হবে কারণ আমরা "95643" -> "95463" -> "45963" এর মতো ব্যবহার করে s কে t এ রূপান্তর করতে পারি।>

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

স্থান :=একটি মানচিত্র যেখানে ডিফল্ট মান প্রকারের তালিকা
s-এর রেঞ্জের সাইজ 0 থেকে নিচের জন্য, করুন
- key :=s[i] পূর্ণসংখ্যা হিসাবে
- জায়গার শেষে i ঢোকান[কী]
প্রতিটি e-এর জন্য t, করুন
- কী :=ই পূর্ণসংখ্যা হিসাবে
  - যদি স্থান [কী] খালি থাকে, তাহলে
    - রিটার্ন ফলস
  - i :=স্থানের শেষ উপাদান[কী]
  - j-এর জন্য রেঞ্জ 0 থেকে কী - 1, করুন
    - যদি স্থানগুলি [j] অ-খালি হয় এবং স্থানগুলির শেষ উপাদান [j]
      - রিটার্ন ফলস
  - স্থান[কী]
    থেকে শেষ উপাদান মুছুন
রিটার্ন ট্রু

উদাহরণ

আরও ভালোভাবে বোঝার জন্য আসুন নিম্নলিখিত বাস্তবায়ন দেখি

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