Kiểm tra xem các ký tự trong một chuỗi có tạo thành một Palindrome trong khoảng trống thừa O (1) trong Python hay không

Giả sử chúng ta có một chuỗi s. Chuỗi này có thể chứa các ký tự viết thường, các ký tự đặc biệt khác và số. Chúng ta phải kiểm tra xem chỉ các chữ cái có trong chuỗi có phải là palindromic hay không. Ở đây có một hạn chế là ở đó chúng tôi không được phép sử dụng thêm dung lượng để giải quyết vấn đề này.

Vì vậy, nếu đầu vào là s =​​"ra $ 5ce58car", thì đầu ra sẽ là True, vì các chữ cái đang tạo thành "racecar" là palindrome.

Để giải quyết vấn đề này, chúng tôi sẽ làm theo các bước sau -

• Xác định một hàm first_letter_index (). Điều này sẽ lấy str, trái, phải
• chỉ mục:=-1
• đối với tôi trong phạm vi từ trái sang phải + 1, thực hiện
  • nếu str [i] là bảng chữ cái viết thường, thì
    • index:=i
    • ra khỏi vòng lặp
• chỉ mục trả lại
• Xác định một hàm last_letter_index (). Điều này sẽ lấy str, trái, phải
• chỉ mục:=-1
• đối với tôi trong phạm vi từ trái sang phải - 1, giảm đi 1, thực hiện
  • nếu str [i] là bảng chữ cái viết thường, thì
    • index:=i
    • ra khỏi vòng lặp
  • chỉ mục trả lại
  • Từ phương thức chính, hãy làm như sau:
  • left:=0, right:=size of str - 1
  • cờ:=True
  • đối với tôi trong phạm vi từ 0 đến kích thước của str, thực hiện
    • left:=first_letter_index (str, left, right)
    • right:=last_letter_index (str, right, left)
    • nếu phải <0 hoặc trái <0, thì
      • ra khỏi vòng lặp
    • nếu str [left] giống str [right], thì
      • left:=left + 1
      • right:=right - 1
      • chuyển sang lần lặp tiếp theo
    • cờ:=Sai
      • ra khỏi vòng lặp
• cờ trả lại

Hãy cùng chúng tôi xem cách triển khai sau để hiểu rõ hơn -

Mã mẫu

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))

Đầu vào

"ra$5ce58car"

Đầu ra

True