ตรวจสอบว่าอักขระในสตริงสร้าง Palindrome ใน O(1) ช่องว่างพิเศษใน Python . หรือไม่

สมมติว่าเรามีสตริง s สตริงนี้สามารถประกอบด้วยอักขระตัวพิมพ์เล็ก อักขระพิเศษอื่นๆ และตัวเลข เราต้องตรวจสอบว่ามีเพียงตัวอักษรที่อยู่ในสตริงเท่านั้นที่เป็นพาลินโดรมหรือไม่ ข้อจำกัดประการหนึ่งคือ เราไม่อนุญาตให้ใช้พื้นที่เพิ่มเติมเพื่อแก้ปัญหานี้

ดังนั้น หากอินพุตเป็น s ="ra$5ce58car" ผลลัพธ์จะเป็น True เนื่องจากตัวอักษรสร้าง "racecar" ซึ่งก็คือ palindrome

เพื่อแก้ปัญหานี้ เราจะทำตามขั้นตอนเหล่านี้ -

• กำหนดฟังก์ชัน first_letter_index() นี่จะใช้เวลา str ซ้าย ขวา
• ดัชนี :=-1
• สำหรับฉันอยู่ในช่วงจากซ้ายไปขวา + 1 ทำ
  • ถ้า str[i] เป็นอักษรตัวพิมพ์เล็ก แล้ว
    • ดัชนี :=ผม
    • ออกมาจากลูป
• ดัชนีผลตอบแทน
• กำหนดฟังก์ชัน last_letter_index() นี่จะใช้เวลา str ซ้าย ขวา
• ดัชนี :=-1
• สำหรับฉันในช่วงจากซ้ายไปขวา - 1 ลดลง 1 ทำ
  • ถ้า str[i] เป็นอักษรตัวพิมพ์เล็ก แล้ว
    • ดัชนี :=ผม
    • ออกมาจากลูป
  • ดัชนีผลตอบแทน
  • จากวิธีหลัก ให้ทำดังนี้:
  • ซ้าย :=0, ขวา :=ขนาดของ str - 1
  • flag :=จริง
  • สำหรับฉันในช่วง 0 ถึงขนาดของ str ทำ
    • ซ้าย :=first_letter_index(str, ซ้าย, ขวา)
    • ขวา :=last_letter_index(str, right, left)
    • ถ้าขวา <0 หรือซ้าย <0 แล้ว
      • ออกมาจากลูป
    • ถ้า str[left] เหมือนกับ str[right] แล้ว
      • ซ้าย :=ซ้าย + 1
      • ขวา :=ขวา - 1
      • ติดตามตอนต่อไป
    • flag :=เท็จ
      • ออกมาจากลูป
• ธงกลับ

ให้เราดูการใช้งานต่อไปนี้เพื่อความเข้าใจที่ดีขึ้น -

โค้ดตัวอย่าง

def first_letter_index(str, left, right):
   index = -1
   for i in range(left, right + 1):
      if str[i] >= 'a' and str[i] <= 'z' :
         index = i
         break
 
   return index

def last_letter_index(str, left, right):
   index = -1
   for i in range(left, right - 1, -1) :
      if str[i] >= 'a' and str[i] <= 'z':
         index = i
         break
 
   return index

def solve(str):
   left = 0
   right = len(str) - 1
   flag = True
 
   for i in range(len(str)) :
      left = first_letter_index(str, left, right)
      right = last_letter_index(str, right, left)
 
      if right < 0 or left < 0:
         break
      if str[left] == str[right]:
         left += 1
         right -= 1
         continue
 
      flag = False
      break
 
   return flag
 
s = "ra$5ce58car"
print(solve(s))

อินพุต

"ra$5ce58car"

ผลลัพธ์

True