文字列内の文字がPythonのO（1）余分なスペースで回文を形成するかどうかを確認します

文字列sがあるとします。この文字列には、小文字、その他の特殊文字、および数字を含めることができます。文字列に含まれる文字だけが回文であるかどうかを確認する必要があります。ここでの1つの制約は、この問題を解決するために余分なスペースを使用することは許可されていないということです。

したがって、入力がs ="ra $ 5ce58car"の場合、文字が回文である "racecar"を形成しているため、出力はTrueになります。

これを解決するには、次の手順に従います-

• 関数first_letter_index（）を定義します。これには、str、left、rightが必要です
• インデックス：=-1
• 左から右+1の範囲のiの場合、実行します
  • str [i]が小文字のアルファベットの場合、
    • インデックス：=i
    • ループから抜け出す
• インデックスを返す
• 関数last_letter_index（）を定義します。これには、str、left、rightが必要です
• インデックス：=-1
• 左から右の範囲のiの場合-1、1ずつ減らします。
  • str [i]が小文字のアルファベットの場合、
    • インデックス：=i
    • ループから抜け出す
  • インデックスを返す
  • メインの方法から次の手順を実行します。
  • 左：=0、右：=strのサイズ-1
  • フラグ：=True
  • 0からstrのサイズの範囲のiについては、
    • 左：=first_letter_index（str、left、right）
    • right：=last_letter_index（str、right、left）
    • 右<0または左<0の場合、
      • ループから抜け出す
    • str[left]がstr[right]と同じ場合、
      • 左：=左+ 1
      • right：=right-1
      • 次の反復に進む
    • フラグ：=False
      • ループから抜け出す
• フラグを返す

理解を深めるために、次の実装を見てみましょう-

サンプルコード

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