判断回文串

判断回文串(hdu 2029)

问题定义: 判断一个字符串是否是回文串（正读和反读都一样）。

算法步骤:

1. 初始化左指针 left = 0，右指针 right = s.length() - 1。
2. 当 left < right 时，进行循环： a. 比较 s[left] 和 s[right]。 b. 如果 s[left] != s[right]，则该字符串不是回文串，返回 false。 c. 如果相等，则继续向中间收缩指针：left++，right--。
3. 如果循环正常结束，说明所有对称位置的字符都相等，返回 true。

复杂度分析:

• 时间复杂度: $O(n)$。
• 空间复杂度: $O(1)$。

证明

直觉的创建一个命题:

• 若 $A$ :$P(i,j)$ 表示字符串 $s[i..j]$ 是回文串
• 则 $B$: $P(i,j) = P(i+1,j-1) \quad \text{且} \quad s[i] == s[j]$
• 一个命题和它的逆否命题等价: $A \to B \Leftrightarrow \neg B \to \neg A$

代码实现

        
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

        #include <string>
#include <iostream>

bool is_palindrome(const string& s) {
    int left = 0;
    int right = s.length() - 1;
    while (left < right) {
        if (s[left] != s[right]) {
            return false;
        }
        left++;
        right--;
    }
    return true;
}