LeetCode 680.验证回文串 II

目录

题目：

题目描述：

题目链接：

思路：

核心思路：

思路详解：

代码：

C++代码：

Java代码：

题目：

题目描述：

题目链接：

680. 验证回文串 II - 力扣（LeetCode）

思路：

核心思路：

双指针

思路详解：

定义i指针指向首位，j指针指向末位，每次将两个指针指向的字符进行比较，如果两个字符相同就i指针后移，j指针前移。由题最多可以从中删除一个字符，我们思考一下发现如果两个指针指向的字符不同我们删除字符存在两种情况，一种是删除左边的字符，另一种是删除右边的字符。这里我们可以利用与运算的性质，只要有一种情况为true就是true，两种情况都为false才是false。所以我们可以再定义一个函数表示删除某边字符再检查的函数，两种删除的情况只需要传入不同的参数即可实现

这题有两个易错点，一个是双指针结束循环的条件，另一个是在参数传递时可能出现的问题，具体可能出现的问题已经在代码注释中详细地进行了解释

代码：

C++代码：

class Solution {
public:
    bool validPalindrome(string s) {
        int i = 0;           //i指针指向首位
        int j = s.size()-1;  //j指针指向末位
        while(i < j)  //这里加不加=都可以过，不加时间还能更快一点
                      //注意不能是i!=j，如果是偶数长度字符串会出现i和j交错永远不相等而死循环
        {
            if(s[i] == s[j])
            {
                i++;
                j--;
            }
            else
            {
                //先检查删除左边字符的情况，在检查删除右边字符的情况
                //两种情况做与运算，有一种为true返回true，如果都为false返回false
                return checkPalindrome(s,i+1,j) || checkPalindrome(s,i,j-1);
                //注意这里容易出现参数传递的问题，如果是i++或者是j--作为参数传递
                //会导致先传递当前值，然后才递增/递减，可能使索引越界
                //正确的是上述方式或者是++i,--j作为参数传递
            }
        }
        return true;  //此处返回true表明没有删除字符，即初始字符串就是回文串
    }

    bool checkPalindrome(string s,int i,int j)  //定义删除某边字符再检查的函数
    {
        while(i < j)
        {
            if(s[i] == s[j])
            {
                i++;
                j--;
            }
            else
            {
                return false;  //题目要求最多可以从中删除一个字符，此时再不满足回文串就返回false
            }
        }
        return true;
    }
};

Java代码：

class Solution {  //注释同理C++代码
    public boolean validPalindrome(String s) {
        int i = 0;
        int j = s.length()-1;
        while(i < j)
        {
            if(s.charAt(i) == s.charAt(j))
            {
                i++;
                j--;
            }
            else
            {
                return checkPalindrome(s,i+1,j) || checkPalindrome(s,i,j-1);
            }
        }
        return true;
    }

    public boolean checkPalindrome(String s,int i,int j)
    {
        while(i < j)
        {
            if(s.charAt(i) == s.charAt(j))
            {
                i++;
                j--;
            }
            else
            {
                return false;
            }
        }
        return true;
    }
}