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种算法的时间复杂度均为： $O(n)$ 。

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

巴特西

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

最新文章

热门文章