680.验证回文串II

LeetCode LeetCode 贪心双指针字符串

发布时间 : 2000-01-10 06:08

字数:1.1k 阅读 :

评论:

680.验证回文串II

680.验证回文串II

680.1 题目

给你一个字符串 s，最多可以从中删除一个字符。

请你判断 s 是否能成为回文字符串：如果能，返回 true；否则，返回 false。

示例 1：

输入：s = "aba"
输出：true

示例 2：

输入：s = "abca"
输出：true
解释：你可以删除字符 ‘c’ 。

示例 3：

输入：s = "abc"
输出：false

提示：

1 <= s.length <= 10^5
s 由小写英文字母组成

680.2 题解

封装后双指针

// 方法一：封装后双指针
// 封装判断是否是回文串的方法
// 两端向中间遍历字符串
// 遇到不相等的字符尝试删除左边或右边的字符，判断剩下的部分是否为回文字符串
static bool CanBePalindrome1(string s)
{
    // 初始化左右指针，左指针指向字符串开头，右指针指向字符串结尾
    int left = 0, right = s.Length - 1;

    // 从两端向中间遍历字符串
    while (left < right)
    {
        // 如果遇到不相等的字符
        if (s[left] != s[right])
        {
            // 尝试删除左边或右边的字符，判断剩下的部分是否为回文字符串
            return IsPalindrome(s, left + 1, right) || IsPalindrome(s, left, right - 1);
        }

        // 移动左指针向右移动一位，右指针向左移动一位
        left++;
        right--;
    }

    // 如果所有字符都匹配，说明字符串本身就是回文字符串
    return true;
}

// 判断指定范围内的字符串是否为回文字符串
static bool IsPalindrome(string s, int left, int right)
{
    // 使用双指针，从指定范围的两端向中间遍历字符串
    while (left < right)
    {
        // 如果两端的字符不相等，则不是回文字符串
        if (s[left] != s[right])
        {
            return false;
        }

        // 移动左指针向右移动一位，右指针向左移动一位，继续检查下一对字符
        left++;
        right--;
    }

    // 如果整个范围内的字符都匹配，说明是回文字符串
    return true;
}

680.3 代码

using System;

class Program
{
    static void Main()
    {
        #region 题目

        // 给你一个字符串 s，最多可以从中删除一个字符。
        // 请你判断 s 是否能成为回文字符串：如果能，返回 true ；否则，返回 false 。

        // 示例 1：
        // 输入：s = "aba"
        // 输出：true

        // 示例 2：
        // 输入：s = "abca"
        // 输出：true
        // 解释：你可以删除字符 'c' 。

        // 示例 3：
        // 输入：s = "abc"
        // 输出：false

        // 提示：
        // 1 <= s.length <= 105
        // s 由小写英文字母组成

        #endregion

        #region 测试

        // 示例 1
        string str1 = "aba";
        bool result1_1 = CanBePalindrome1(str1);
        Console.WriteLine($"示例1 方法1 输出：{result1_1}");

        // 示例 2
        string str2 = "abca";
        bool result2_1 = CanBePalindrome1(str2);
        Console.WriteLine($"示例2 方法1 输出：{result2_1}");

        // 示例 3
        string str3 = "abc";
        bool result3_1 = CanBePalindrome1(str3);
        Console.WriteLine($"示例3 方法1 输出：{result3_1}");

        #endregion
    }

    #region 答案

    // 方法一：双指针
    // 封装判断是否是回文串的方法
    // 两端向中间遍历字符串
    // 遇到不相等的字符尝试删除左边或右边的字符，判断剩下的部分是否为回文字符串
    static bool CanBePalindrome1(string s)
    {
        // 初始化左右指针，左指针指向字符串开头，右指针指向字符串结尾
        int left = 0, right = s.Length - 1;

        // 从两端向中间遍历字符串
        while (left < right)
        {
            // 如果遇到不相等的字符
            if (s[left] != s[right])
            {
                // 尝试删除左边或右边的字符，判断剩下的部分是否为回文字符串
                return IsPalindrome(s, left + 1, right) || IsPalindrome(s, left, right - 1);
            }

            // 移动左指针向右移动一位，右指针向左移动一位
            left++;
            right--;
        }

        // 如果所有字符都匹配，说明字符串本身就是回文字符串
        return true;
    }

    // 判断指定范围内的字符串是否为回文字符串
    static bool IsPalindrome(string s, int left, int right)
    {
        // 使用双指针，从指定范围的两端向中间遍历字符串
        while (left < right)
        {
            // 如果两端的字符不相等，则不是回文字符串
            if (s[left] != s[right])
            {
                return false;
            }

            // 移动左指针向右移动一位，右指针向左移动一位，继续检查下一对字符
            left++;
            right--;
        }

        // 如果整个范围内的字符都匹配，说明是回文字符串
        return true;
    }

    #endregion
}

680.4 运行结果

示例1 方法1 输出：True
示例2 方法1 输出：True
示例3 方法1 输出：False

转载请注明来源，欢迎对文章中的引用来源进行考证，欢迎指出任何有错误或不够清晰的表达。可以在下面评论区评论，也可以邮件至 785293209@qq.com