學習路線/雙指標

125. 驗證迴文串

Easy

Valid Palindrome

Two PointersString

題目描述

給定一個字串 s，判斷它是否為迴文串。只考慮字母和數字字元，忽略大小寫。例如 "A man, a plan, a canal: Panama" 是迴文。

LeetCode 125原題連結 →

解法思路

  1. 使用左右雙指針分別從字串首尾開始向中間移動
  2. 跳過非字母數字的字元（空格、標點等）
  3. 將兩端字元轉為小寫後比較，若不同則不是迴文
  4. 兩指針相遇時仍未發現不同，則確認為迴文

複雜度分析

  • 時間複雜度：O(n)
  • 空間複雜度：O(1)

字串 s

A
0
⎵
1
m
2
a
3
n
4
,
5
⎵
6
a
7
⎵
8
p
9
l
10
a
11
n
12
,
13
⎵
14
a
15
⎵
16
c
17
a
18
n
19
a
20
l
21
:
22
⎵
23
P
24
a
25
n
26
a
27
m
28
a
29
Left [0]Right [29]
初始化雙指針：Left → 0，Right → 29。開始從兩端向內收縮。
1 / 33