C#LeetCode刷题之#680-验证回文字符串 Ⅱ（Valid Palindrome II）

问题

给定一个非空字符串 s，最多删除一个字符。判断是否能成为回文字符串。

输入: "aba"

输出: True

输入: "abca"

输出: True

解释: 你可以删除c字符。

注意:字符串只包含从 a-z 的小写字母。字符串的最大长度是50000。

Given a non-empty string s, you may delete at most one character. Judge whether you can make it a palindrome.

Input: "aba"

Output: True

Input: "abca"

Output: True

Explanation: You could delete the character 'c'.

Note:The string will only contain lowercase characters a-z. The maximum length of the string is 50000.

示例

public class Program {

    public static void Main(string[] args) {

        var s = "abca";

        var res = ValidPalindrome(s);

        Console.WriteLine(res);

        s = "Iori's Blog!";

        res = ValidPalindrome2(s);

        Console.WriteLine(res);

        Console.ReadKey();

    }

    private static bool ValidPalindrome(string s) {

        //暴力解法，超时未AC

        if(IsPalindrome(s)) return true;

        for(int i = 0; i < s.Length; i++) {

            var substring = s.Remove(i, 1);

            if(IsPalindrome(substring)) return true;

        }

        return false;

    }

    private static bool IsPalindrome(string s) {

        //前后双指针法

        var i = 0;

        var j = s.Length - 1;

        while(i < j) {

            if(s[i] != s[j]) return false;

            i++;

            j--;

        }

        return true;

    }

    public static bool ValidPalindrome2(String s) {

        var i = -1;

        var j = s.Length;

        while(++i < --j)

            //不相同时，并不代表就不是回文了，因为有删除一个字符的机会

            //但我们不知道往前删除还是往后删除

            //所以我们前后各判定一次

            if(s[i] != s[j])

                return IsPalindrome2(s, i, j - 1) || IsPalindrome2(s, i + 1, j);

        return true;

    }

    private static bool IsPalindrome2(String s, int i, int j) {

        while(i < j) if(s[i++] != s[j--]) return false;

        return true;

    }

}

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

True

False

分析：

显而易见，ValidPalindrome 的时间复杂度为： $O(n^{2})$ ，ValidPalindrome2 的时间复杂度为： $O(n)$ 。

巴特西

C#LeetCode刷题之#680-验证回文字符串 Ⅱ（Valid Palindrome II）

最新文章

热门文章

巴特西

C#LeetCode刷题之#680-验证回文字符串 Ⅱ​​​​​​​（Valid Palindrome II）

最新文章

热门文章

C#LeetCode刷题之#680-验证回文字符串 Ⅱ（Valid Palindrome II）