C#LeetCode刷题之#125-验证回文串（Valid Palindrome）

问题

给定一个字符串，验证它是否是回文串，只考虑字母和数字字符，可以忽略字母的大小写。

说明：本题中，我们将空字符串定义为有效的回文串。

输入: “A man, a plan, a canal: Panama”

输出: true

输入: “race a car”

输出: false

Given a string, determine if it is a palindrome, considering only alphanumeric characters and ignoring cases.

Note: For the purpose of this problem, we define empty string as valid palindrome.

Input: “A man, a plan, a canal: Panama”

Output: true

Input: “race a car”

Output: false

示例

public class Program {

    public static void Main(string[] args) {
        var s = "0P";

        var res = IsPalindrome(s);
        Console.WriteLine(res);

        s = "A man, a plan, a canal: Panama";

        res = IsPalindrome2(s);
        Console.WriteLine(res);

        Console.ReadKey();
    }

    private static bool IsPalindrome(string s) {
        //基本思路，反转字符串后判定和之前是否相同
        //LeetCode超时未AC
        s = FilterCharacter(s);
        var reverse = "";
        s.Reverse().ToList().ForEach(c => reverse += c);
        return s == reverse;
    }

    /// <summary>
    /// 过滤非字母以外的字符串
    /// </summary>
    /// <returns>过滤后的字符串</returns>
    /// <param name="s">待过滤的字符串</param>
    private static string FilterCharacter(string s) {
        var res = string.Empty;
        s = s.ToLower().Trim();
        s.ToList().ForEach(c => {
            if((c >= 48 && c <= 57) ||
               (c >= 97 && c <= 122)) res += c;
        });
        return res;
    }

    private static bool IsPalindrome2(string s) {
        //基本思路，先用List存放所有符合条件的字符
        //再比较前半部分和后半部分
        s = s.ToLower().Trim();
        var list = new List<char>();
        foreach(var c in s) {
            if((c >= 48 && c <= 57) ||
               (c >= 97 && c <= 122)) {
                list.Add(c);
            }
        }
        var mid = list.Count / 2;
        for(var i = 0; i < mid; i++) {
            if(list[i] != list[list.Count - i - 1]) return false;
        }
        return true;
    }

}

以上给出2种算法实现，以下是这个案例的输出结果：

False
True

分析：

显而易见，以上2种算法的时间复杂度均为：  。

需要注意的是，虽然以上2种算法的时间复杂度相同，但是 IsPalindrome2 的执行效率明显更高，因为只有1.5次遍历，并且比较部分使用了效率较高的数据结构 List；IsPalindrome 有反转字符串和去除不合法字符的代码，所以至少需要遍历2次。IsPalindrome2 是典型的空间换时间算法。