题目：

如果在将所有大写字符转换为小写字符、并移除所有非字母数字字符之后，短语正着读和反着读都一样。则可以认为该短语是一个 回文串 。

字母和数字都属于字母数字字符。

给你一个字符串 s，如果它是 回文串 ，返回 true ；否则，返回 false 。

 

示例 1：

输入: s = "A man, a plan, a canal: Panama"

输出：true

解释："amanaplanacanalpanama" 是回文串。

示例 2：

输入：s = "race a car"

输出：false

解释："raceacar" 不是回文串。

示例 3：

输入：s = " "

输出：true

解释：在移除非字母数字字符之后，s 是一个空字符串 "" 。

由于空字符串正着反着读都一样，所以是回文串。

 

提示：

1 <= s.length <= 2 * 105

s 仅由可打印的 ASCII 字符组成

链接：https://leetcode.cn/problems/valid-palindrome

解法1：反转字符串

如果一个字符串是一个回文串，那么将这个回文串反转后还是自己本身

  • 处理字符串，将数字和字母去除，并将大小写修改一致

  • 反转字符串并判断是否和自己本身一致

复杂度分析

  • 时间复杂度：O(n)

  • 空间复杂度：O(n)

    public bool IsPalindrome(string s)
    {
        var newS = "";
        for (int i = 0; i < s.Length; i++)
        {
            if (char.IsLetterOrDigit(s[i]))
                newS += char.ToLower(s[i]);
        }
        return newS.Equals(new string(newS.Reverse().ToArray()));
    }

解法2：双指针(更优)

  • 创建一个头指针，一个尾指针，分别从头尾开始向中间逼近

  • 两指针分别取合法的字符并统一大小写后进行比较

  • 若不同，则直接返回false

  • 当两个指针相遇时，说明字符串为回文，返回true

复杂度分析

  • 时间复杂度：O(n)

  • 空间复杂度：O(1)

    public bool IsPalindrome(string s)
    {
        int head = 0;
        int tail = s.Length - 1;
        while (head < tail)
        {
            while (head < tail && !char.IsLetterOrDigit(s[head]))
                head++;
            while (head < tail && !char.IsLetterOrDigit(s[tail]))
                tail--;
            if (char.ToLower(s[head]) != char.ToLower(s[tail]))
                return false;
            head++;
            tail--;
        }
        return true;
    }