125. Valid Palindrome
回文的題目真的滿常讓我掛掉的，所以我想要記錄下來我怎麼克服這類型的題型的
雙指針
雙指針是一個很好想到的解法，從兩側往中間搜尋，終止條件是兩邊的指針到達中間位置了。
這裡是一個小地方要注意，那就是 while 的執行條件是要用 left < right 還是要用 left <= right ?
如果是 left < right 的話，代表的是當 left 大於或等於 right 的時候， while 就不再執行了 。這時候有兩種情況：
- 第一種是字串是偶數，指針到最中間的時候，兩個指針再繼續下一步時，分別會跨中中間點，那其實就代表了左側與右側的字元都檢查完畢了
- 第二種是字串是奇數，指針到最中間的時候，兩個指針再繼續下一步時，會兩個點都剛好在中間點上面，這時候就達到了
while的終止條件，我們會少比較了一種情況，可是這個情況並不重要，因為兩個指針指在同一個字元上面，那該字元不管如何，都一定會相等，還是會滿足回文的條件。
如果是 left <= right 的情況，代表 left 要大於 right 才會終止 while 的執行，一樣可以思考兩種情況：
- 第一種是字串是偶數，指針到最中間的時候，兩個指針再繼續下一步時，分別會跨中中間點，那其實就代表了左側與右側的字元都檢查完畢了。和前一個情況一模一樣。
- 第二種是字串是奇數，其實就是補足了上一個情況中，最後沒有檢查到的最後一個字元，所以也是可以的。
class Solution:
def isPalindrome(self, s: str) -> bool:
s = "".join([c.lower() for c in s if c.isalnum()])
left = 0
right = len(s) - 1
while left <= right:
if s[left] != s[right]:
return False
left += 1
right -= 1
return True
遞迴
了解後，其實這個題目也可以用遞迴的方式來寫，前面的鋪陳就是要寫出遞迴的終止條件：
遞迴的方式是我們不斷往中間去靠近，如果有出現錯誤的話，就會回傳 False ，最後一步就是當兩邊的指針分別跨越中線之後，就代表一定是一個回文，回傳 True 。其思考的模式和前面雙指針的方式相同。
class Solution:
def isPalindrome(self, s: str) -> bool:
s = "".join([c.lower() for c in s if c.isalnum()])
def helper(left, right):
if left >= right:
return True
if s[left] == s[right]:
return helper(left+1, right-1)
if s[left] != s[right]:
return False
return helper(0, len(s)-1)
中心擴散法
最後還有一個前言有提到的從中心往左右延伸的情況，其重要注意的是，如果今天的字串是偶數，向右出發的指針需要比 mid 多 1 。
class Solution:
def isPalindrome(self, s: str) -> bool:
s = "".join([c.lower() for c in s if c.isalnum()])
mid = (len(s)-1) // 2
left = mid
right = mid
if len(s) % 2 == 0:
left = mid
right = mid + 1
while left >= 0 and right < len(s):
if s[left] != s[right]:
return False
left -= 1
right += 1
return True