আমরা পাইথনে একটি স্ট্রিংকে ক্রমাগত অবরোহী মানগুলিতে বিভক্ত করতে পারি কিনা তা পরীক্ষা করার জন্য প্রোগ্রাম

ধরুন আমাদের একটি স্ট্রিং s আছে শুধুমাত্র সংখ্যা সহ। আমাদের পরীক্ষা করতে হবে যে আমরা s কে দুটি বা ততোধিক অ-খালি সাবস্ট্রিং-এ বিভক্ত করতে পারি যেমন সেই সাবস্ট্রিংগুলির সংখ্যাসূচক মানগুলি অ-ক্রমবর্ধমান ক্রমানুসারে এবং প্রতিটি দুটি সন্নিহিত সাবস্ট্রিংগুলির সংখ্যাসূচক মানের মধ্যে পার্থক্য হল 1। সুতরাং উদাহরণস্বরূপ, যদি স্ট্রিংটি হল s ="0080079" আমরা এটিকে ["0080", "079"] সংখ্যাসূচক মান [80, 79] এ বিভক্ত করতে পারি। এবং মানগুলি অবরোহী ক্রমে এবং সংলগ্ন মানগুলি 1 দ্বারা পৃথক, তাই এই উপায়টি বৈধ। উপরে বর্ণিত হিসাবে s বিভক্ত করা সম্ভব কি না তা আমাদের পরীক্ষা করতে হবে।

সুতরাং, যদি ইনপুটটি s ="080076" এর মতো হয়, তবে আউটপুটটি True হবে কারণ আমরা এটিকে ["08", "007", "6"] এর মতো বিভক্ত করতে পারি, তাই সংখ্যাসূচক মানগুলি হল [8,7,6] .

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

• একটি ফাংশন dfs() সংজ্ঞায়িত করুন। এর জন্য s, pre, idx, n

  লাগবে

• যদি pre-1 না হয় এবং (s[index idx থেকে শেষ পর্যন্ত] এর সাবস্ট্রিং) এর পূর্ণসংখ্যার রূপ প্রি-1-এর মতো হয়, তাহলে

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

• আমি 1 থেকে n-idx-1 রেঞ্জের জন্য, কর

  • curs :=s এর সাবস্ট্রিং [index idx থেকে idx+i-1]

  • cur :=সংখ্যা হিসাবে curs

  • যদি pre-1 এর মত হয়, তাহলে

    • যদি dfs(s, cur, idx+i, n) সত্য হয়, তাহলে

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

    • অন্যথায়,

      • যদি cur হয় প্রি - 1 এবং dfs(s, cur, idx+i, n) সত্য হয়, তাহলে

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

• রিটার্ন ফলস

• প্রধান পদ্ধতি থেকে, নিম্নলিখিতগুলি করুন

• n :=s

  এর আকার

• যদি n <=1, তাহলে

  • রিটার্ন ফলস

• dfs(s, -1, 0, n)

  ফেরত দিন

উদাহরণ

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

def dfs(s, pre, idx, n):
   if pre != -1 and int(s[idx:]) == pre - 1:
      return True
   for i in range(1, n-idx):
      curs = s[idx: idx+i]
      cur = int(curs)
      if pre == -1:
         if dfs(s, cur, idx+i, n):
            return True
      else:
         if cur == pre - 1 and dfs(s, cur, idx+i, n):
            return True
   return False

def solve(s):
   n = len(s)
   if n <= 1:
      return False
   return dfs(s, -1, 0, n)

s = "080076"
print(solve(s))

ইনপুট

"080076"

আউটপুট

True