开发者社区> 李博 bluemind> 正文
阿里云
为了无法计算的价值
打开APP
阿里云APP内打开

[LeetCode] Valid Palindrome II 验证回文字符串之二

简介:
+关注继续查看

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

Example 1:

Input: "aba"
Output: True

Example 2:

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

Note:

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

这道题是之前那道Valid Palindrome的拓展,还是让我们验证回复字符串,但是区别是这道题的字符串中只含有小写字母,而且这道题允许删除一个字符,那么当遇到不匹配的时候,我们到底是删除左边的字符,还是右边的字符呢,我们的做法是两种情况都要算一遍,只要有一种能返回true,那么结果就返回true。我们可以写一个子函数来判断字符串中的某一个范围内的子字符串是否为回文串,参见代码如下:

解法一:

public:
    bool validPalindrome(string s) {
        int left = 0, right = s.size() - 1;
        while (left < right) {
            if (s[left] != s[right]) return isValid(s, left, right - 1) || isValid(s, left + 1, right);
            ++left; --right;
        }
        return true;
    }
    bool isValid(string s, int left, int right) {
        while (left < right) {
            if (s[left] != s[right]) return false;
            ++left; --right;
        }
        return true;
    }
};

下面这种写法跟上面的解法思路一样,只不过没有写额外的函数,还是要遍历两种情况,参见代码如下:

解法二:

public:
    bool validPalindrome(string s) {
        int left = 0, right = s.size() - 1;
        while (left < right) {
            if (s[left] == s[right]) {
                ++left; --right;
            } else {
                int l = left, r = right - 1;
                while (l < r) {
                    if (s[l] != s[r]) break;
                    ++l; --r;
                    if (l >= r) return true;
                }
                ++left;
                while (left < right) {
                    if (s[left] != s[right]) return false;
                    ++left; --right;
                }
            }
        }
        return true;
    }
};

参考资料:

https://discuss.leetcode.com/topic/103939/java-o-n-time-o-1-space

https://discuss.leetcode.com/topic/103911/two-solutions-optimized-and-recursive-java-and-c

本文转自博客园Grandyang的博客,原文链接:[LeetCode] Valid Palindrome II 验证回文字符串之二

,如需转载请自行联系原博主。

版权声明:本文内容由阿里云实名注册用户自发贡献,版权归原作者所有,阿里云开发者社区不拥有其著作权,亦不承担相应法律责任。具体规则请查看《阿里云开发者社区用户服务协议》和《阿里云开发者社区知识产权保护指引》。如果您发现本社区中有涉嫌抄袭的内容,填写侵权投诉表单进行举报,一经查实,本社区将立刻删除涉嫌侵权内容。

相关文章
【LeetCode】二叉树的序列化与反序列化 | 验证二叉树的前序序列化
【LeetCode】二叉树的序列化与反序列化 | 验证二叉树的前序序列化
0 0
LeetCode 680. 验证回文字符串 Ⅱ
给定一个非空字符串 s,最多删除一个字符。判断是否能成为回文字符串。
0 0
LeetCode 125. 验证回文串
给定一个字符串,验证它是否是回文串,只考虑字母和数字字符,可以忽略字母的大小写。
0 0
LeetCode contest 177 5170. 验证二叉树
LeetCode contest 177 5170. 验证二叉树
0 0
代码随想录刷题|LeetCode 654.最大二叉树 617.合并二叉树 700.二叉搜索树中的搜索 98.验证二叉搜索树
代码随想录刷题|LeetCode 654.最大二叉树 617.合并二叉树 700.二叉搜索树中的搜索 98.验证二叉搜索树
0 0
LeetCode 680.验证回文字符串 Ⅱ(双指针法)
LeetCode 680.验证回文字符串 Ⅱ(双指针法)
0 0
LeetCode每日一题——946. 验证栈序列
给定 pushed 和 popped 两个序列,每个序列中的 值都不重复,只有当它们可能是在最初空栈上进行的推入 push 和弹出 pop 操作序列的结果时,返回 true;否则,返回 false 。
0 0
LeetCode每日一题——953. 验证外星语词典
某种外星语也使用英文小写字母,但可能顺序 order 不同。字母表的顺序(order)是一些小写字母的排列。
0 0
【day10】LeetCode(力扣)刷题(注释详细)[707.设计链表][278.第一个错误的版本][98. 验证二叉搜索树]
刷题(注释详细)[707.设计链表][278.第一个错误的版本][98. 验证二叉搜索树]。
0 0
LeetCode 98验证二叉搜素树(中序遍历)&99恢复二叉搜索树
给定一个二叉树,判断其是否是一个有效的二叉搜索树。
0 0
+关注
李博 bluemind
云栖社区Java、Redis、MongoDB运营小编,有意合作请联系钉钉:15810436147
文章
问答
文章排行榜
最热
最新
相关电子书
更多
低代码开发师(初级)实战教程
立即下载
阿里巴巴DevOps 最佳实践手册
立即下载
冬季实战营第三期:MySQL数据库进阶实战
立即下载