สมมติว่ามีสตริง s ที่ประกอบด้วยตัวเลข เราต้องตรวจสอบว่ามันมีตัวเลขจำนวนเต็มที่เรียงลดลงติดกันหรือไม่
เช่น ถ้าอินพุตคือ s = "99989796" ผลลัพธ์จะเป็น True เนื่องจากสตริงนี้ประกอบด้วย [99,98,97,96]
ขั้นตอนการแก้ปัญหา
- กำหนดฟังก์ชัน helper() รับ pos, prev_num
- ถ้า pos == n คืนค่า True
- num_digits := จำนวนหลักของ prev_num
- for i ในช่วง num_digits-1 ถึง num_digits
- ถ้า s[pos:pos+i] และ int(s[pos:pos+i]) == prev_num - 1 ถ้า helper(pos+i, prev_num-1) คืนค่า True
- คืนค่า False
- จากเมธอดหลัก n := len(s) for i ใน 1 ถึง n//2 num := int(s[:i]) ถ้า helper(i, num) คืนค่า True
- คืนค่า False
ตัวอย่างโค้ด
class Solution:
def solve(self, s):
n = len(s)
def helper(pos, prev_num):
if pos == n:
return True
num_digits = len(str(prev_num))
for i in range(num_digits - 1, num_digits + 1):
if s[pos:pos+i] and int(s[pos:pos+i]) == prev_num - 1:
if helper(pos + i, prev_num - 1):
return True
return False
for i in range(1, n//2 + 1):
num = int(s[:i])
if helper(i, num):
return True
return False
ob = Solution()
s = "99989796"
print(ob.solve(s))
อินพุต
"99989796"
เอาต์พุต
True
