C#LeetCode刷题之#125-验证回文串(Valid Palindrome)

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 是典型的空间换时间算法。

本文由 .Net中文网 原创发布,欢迎大家踊跃转载。

转载请注明本文地址:https://www.byteflying.com/archives/3899

发表评论

登录后才能评论