检查字符串中的字符是否在 Python 中的 O(1) 额外空间中形成回文

假设我们有一个字符串 s。该字符串可以包含小写字符、其他特殊字符和数字。我们必须检查是否只有字符串中出现的字母是回文的。这里的一个限制是我们不允许使用额外的空间来解决这个问题。

因此，如果输入类似于 s = "ra$5ce58car"，则输出将为 True，因为这些字母正在形成回文的“racecar”。

让我们看看以下实现以获得更好的理解 -

示例代码

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