মনে করুন s শুধু নাম্বার সহ একটি স্ট্রিং। আমাদের চেক করতে হবে কি s কে দুটি বা অধিক নন-এম্পটি সাবস্ট্রিংএ ভাগ করা যায় যাতে সাবস্ট্রিংগুলোর নাম্বারিক ভ্যালু নন-ইনক্রিজিং সিকোয়েন্সে থাকে এবং প্রতিটি দুটি আসলেই সাবস্ট্রিংর নাম্বারিক ভ্যালুর পার্থক্য ১। উদাহরণস্বরূপ, যদি স্ট্রিং s = "0080079" হয় তবে আমরা এটিকে ["0080", "079"]-এ ভাগ করতে পারি যাদের নাম্বারিক ভ্যালু [80, 79]। এখানে ভ্যালুগুলো ডিসেন্ডিং অর্ডারে এবং আসলেই ভ্যালুর পার্থক্য ১, তাই এই পদ্ধতি বৈধ। আমাদের চেক করতে হবে s কে উপরে বর্ণিতভাবে ভাগ করা সম্ভব কিনা।
সুতরাং, যদি ইনপুট হয় s = "080076", তবে আউটপুট হবে True কারণ আমরা এটিকে ["08", "007", "6"]-এ ভাগ করতে পারি, তাই নাম্বারিক ভ্যালু [8,7,6]।
এটি সমাধান করতে আমরা নিচের ধাপগুলো অনুসরণ করব −
একটি dfs() ফাংশন ডিফাইন করুন। এটি s, pre, idx, n নেবে
যদি pre != -1 এবং int(s[idx:]) == pre - 1 হয়, তবে
True রিটার্ন করুন
i = 1 থেকে n-idx-1 পর্যন্ত জন্য, করুন
curs := s[idx: idx+i] সাবস্ট্রিং
cur := curs নম্বর হিসেবে
যদি pre == -1 হয়, তবে
যদি dfs(s, cur, idx+i, n) true হয়, তবে
True রিটার্ন করুন
অন্যথায়,
যদি cur == pre - 1 এবং dfs(s, cur, idx+i, n) true হয়, তবে
True রিটার্ন করুন
False রিটার্ন করুন
মেইন মেথড থেকে, নিচের কাজ করুন
n := s-এর আকার
যদি n <= 1 হয়, তবে
False রিটার্ন করুন
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
