寒光博客

[LeetCode]680. 验证回文字符串 Ⅱ
题目 Input: "abca" Output: True Explanation: You could dele...
扫描右侧二维码阅读全文
21
2020/06

[LeetCode]680. 验证回文字符串 Ⅱ

题目

Input: "abca"
Output: True
Explanation: You could delete the character 'c'.

题目描述:可以删除一个字符,判断是否能构成回文字符串。
https://leetcode-cn.com/problems/valid-palindrome-ii/description/

分析

所谓的回文字符串,是指具有左右对称特点的字符串,例如 "abcba" 就是一个回文字符串。

使用双指针可以很容易判断一个字符串是否是回文字符串:令一个指针从左到右遍历,一个指针从右到左遍历,这两个指针同时移动一个位置,每次都判断两个指针指向的字符是否相同,如果都相同,字符串才是具有左右对称性质的回文字符串。

本题的关键是处理删除一个字符。在使用双指针遍历字符串时,如果出现两个指针指向的字符不相等的情况,我们就试着删除一个字符,再判断删除完之后的字符串是否是回文字符串。

在判断是否为回文字符串时,我们不需要判断整个字符串,因为左指针左边和右指针右边的字符之前已经判断过具有对称性质,所以只需要判断中间的子字符串即可。

在试着删除字符时,我们既可以删除左指针指向的字符,也可以删除右指针指向的字符。

代码

正确

 public boolean validPalindrome(String s) {
        char[] str = s.toCharArray();
        for (int i = 0, j = s.length() - 1; i < j; i++, j--) {
            if (str[i] != str[j]) {
                return isPalindrome(str, i + 1, j) || isPalindrome(str, i, j - 1);//分支
            }
        }
        return true;//如果没有分支
    }
    private boolean isPalindrome(char[] str, int i, int j) {
        while (i < j) {
            if (str[i++] != str[j--]) {//注意 j-- 不小心打错饿了
                return false;
            }
        }
        return true;
    }

反思

错误解法
思路有问题,考虑的不全 很暴力 红了五次 出一次bug 修复一下,,
致命问题 只知道当前这一步 和下一步可以成功 但是后续的能否成功不知道 万一 第一个if的是 后续的不回文 第二个的是回文就糟糕了
ebcbb ececabbacec bbcbe
删除 e c都可以 先判断的就可能是死路 所以【在删除之后 重新当做的字符串开始判断】 如正解

public boolean error_validPalindrome(String s) {
        char[] str = s.toCharArray();
        int i = 0, j = s.length() - 1;
        boolean flag = true;
        while (i <= j) {
            if ((str[i] == str[j])) {
                i++;
                j--;
            } else if (flag) { //致命问题 只知道当前这一步 和下一步可以成功 但是后续的能否成功不知道 万一 第一个if的是 后续的不回文 第二个的是回文就糟糕了
                //ebcbb ececabbacec bbcbe   删除 e c都可以 先判断的就可能是死路 所以【在删除之后 重新当做的字符串开始判断】
                if (j - 1 >= i && str[i] == str[j - 1]) {//可以删去
                    i++;
                    j -= 2;
                    flag = false;
                } else if (i + 1 <= j && str[i + 1] == str[j]) {//i删去
                    j--;
                    i += 2;
                    flag = false;
                } else
                    return false;
            } else {
                return false;
            }
        }
        return true;
    }
本文作者:Author:     文章标题:[LeetCode]680. 验证回文字符串 Ⅱ
本文地址:http://dxoca.cn/Algorithm/360.html       百度已收录
版权说明:若无注明,本文皆为“Dxoca's blog (寒光博客)”原创,转载请保留文章出处。
Last modification:June 22nd, 2020 at 08:15 pm
如果觉得我的文章对你有用,请随意赞赏

Leave a Comment