โปรแกรมตรวจสอบว่าเราสามารถแยกสตริงเป็นค่าที่ต่อเนื่องกันจากมากไปหาน้อยใน Python . ได้หรือไม่

สมมติว่าเรามีสตริง s ที่มีตัวเลขเท่านั้น เราต้องตรวจสอบว่าเราสามารถแยก s เป็นสตริงย่อยที่ไม่ว่างเปล่าสองสตริงหรือมากกว่านั้นได้หรือไม่ โดยให้ค่าตัวเลขของสตริงย่อยเหล่านั้นอยู่ในลำดับที่ไม่เพิ่มขึ้น และความแตกต่างระหว่างค่าตัวเลขของทุกๆ สตริงย่อยที่อยู่ติดกัน 2 รายการคือ 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[จากดัชนี idx ถึง end]) จะเหมือนกับ pre -1 ดังนั้น

  • คืนค่า True

• สำหรับฉันอยู่ในช่วง 1 ถึง n-idx-1 ทำ

  • curs :=สตริงย่อยของ s[จากดัชนี idx ถึง idx+i-1]

  • cur :=curs เป็นตัวเลข

  • ถ้า pre เหมือนกับ -1 แล้ว

    • ถ้า dfs(s, cur, idx+i, n) เป็นจริง ดังนั้น

      • คืนค่า True

    • มิฉะนั้น

      • ถ้า cur เหมือนกับ pre - 1 และ dfs(s, cur, idx+i, n) เป็นจริง ดังนั้น

        • คืนค่า True

• คืนค่าเท็จ

• จากวิธีหลัก ให้ทำดังนี้

• 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