用Python檢查字串中的字元是否構成迴文，且額外空間複雜度為O(1)

假設我們有一個字串s。這個字串可以包含小寫字元、其他特殊字元和數字。我們必須檢查字串中存在的字母是否構成迴文。這裡有一個限制，即我們不允許使用額外的空間來解決這個問題。

因此，如果輸入類似於s = "ra$5ce58car"，則輸出將為True，因為字母構成“racecar”，這是一個迴文。

為了解決這個問題，我們將遵循以下步驟：

• 首先定義一個函式`first_letter_index()`。它將接收`str`、`left`和`right`作為引數。
• `index := -1`
• for i in range(left, right + 1):
  • 如果str[i]是小寫字母，則
    • `index := i`
    • 跳出迴圈
• 返回index
• 定義一個函式`last_letter_index()`。它將接收`str`、`left`和`right`作為引數。
• `index := -1`
• for i in range(right, left -1, -1):
  • 如果str[i]是小寫字母，則
    • `index := i`
    • 跳出迴圈
  • 返回index
  • 從主方法執行以下操作：
  • `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)`
    • 如果`right < 0` 或 `left < 0`，則
      • 跳出迴圈
    • 如果`str[left]`等於`str[right]`，則
      • `left := left + 1`
      • `right := right - 1`
      • 進行下一次迭代
    • `flag := False`
      • 跳出迴圈
• 返回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

Arnab Chakraborty

更新於：2021年1月15日

443 次瀏覽

開啟您的職業生涯

完成課程後獲得認證

開始學習