当前位置 : 首页 » 文章分类 :  算法  »  LeetCode.680.Valid Palindrome II 验证回文字符串 Ⅱ

LeetCode.680.Valid Palindrome II 验证回文字符串 Ⅱ

题目描述

680 Valid Palindrome II
https://leetcode-cn.com/problems/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:The string will only contain lowercase characters a-z. The maximum length of the string is 50000.


解题过程

和判断字符串是否回文的方法一样,左右双指针 left,right 向中间移动并比较,当字符不同时,分别尝试跳过 left 指针下的字符和跳过 right 指针下的字符后比较剩余字符串是否回文,如果其中任意子串是回文则结果是回文。

时间复杂度 O(n),空间复杂度 O(1)

private static class SolutionV202005 {
    public boolean validPalindrome(String s) {
        if (null == s || s.length() < 2) {
            return true;
        }
        char[] chars = s.toCharArray();
        for (int i = 0, j = chars.length-1; i <= j; i++, j--) {
            if (chars[i] != chars[j]) {
                // i+1 表示跳过 i 下标处的字符,j-1 表示跳过 j 下标处的字符,继续比较
                return isPalindrome(chars, i+1, j) || isPalindrome(chars, i, j-1);
            }
        }
        return true;
    }

    // 判断 chars[start...end] 是否回文
    private boolean isPalindrome(char[] chars, int start, int end) {
        for (int i = start, j = end; i <= j; i++, j--) {
            if (chars[i] != chars[j]) {
                return false;
            }
        }
        return true;
    }
}

GitHub代码

algorithms/leetcode/leetcode/_680_ValidPalindrome2.java
https://github.com/masikkk/algorithms/blob/master/leetcode/leetcode/_680_ValidPalindrome2.java


上一篇 LeetCode.1371.Find the Longest Substring Containing Vowels in Even Counts 每个元音包含偶数次的最长子字符串

下一篇 LeetCode.210.Course Schedule II 课程表 II

阅读
评论
317
阅读预计2分钟
创建日期 2020-05-19
修改日期 2020-05-19
类别

页面信息

location:
protocol:
host:
hostname:
origin:
pathname:
href:
document:
referrer:
navigator:
platform:
userAgent:

评论