680. 验证回文字符串 Ⅱ


680. 验证回文字符串 Ⅱ

难度简单 324
给定一个非空字符串 s最多删除一个字符。判断是否能成为回文字符串。
示例 1:
输入: “aba”
输出: True

示例 2:
输入: “abca”
输出: True
解释: 你可以删除 c 字符。

class Solution {
    public boolean validPalindrome(String s) {
        int low = 0, high = s.length() - 1;
        while (low < high) &#123;
            char c1 = s.charAt(low), c2 = s.charAt(high);
            if (c1 == c2) &#123;
                ++low;
                --high;
            &#125; else &#123;
                return validPalindrome(s, low, high - 1) || validPalindrome(s, low + 1, high);
            &#125;
        &#125;
        return true;
    &#125;

    public boolean validPalindrome(String s, int low, int high) &#123;
        for (int i = low, j = high; i < j; ++i, --j) &#123;
            char c1 = s.charAt(i), c2 = s.charAt(j);
            if (c1 != c2) &#123;
                return false;
            &#125;
        &#125;
        return true;
    &#125;

// 作者:LeetCode-Solution
// 链接:https://leetcode-cn.com/problems/valid-palindrome-ii/solution/yan-zheng-hui-wen-zi-fu-chuan-ii-by-leetcode-solut/
&#125;

复杂度分析

时间复杂度:O(n),其中 n 是字符串的长度。判断整个字符串是否是回文字符串的时间复杂度是
O(n),遇到不同字符时,判断两个子串是否是回文字符串的时间复杂度也都是 O(n)。
空间复杂度:O(1)。只需要维护有限的常量空间。


文章作者:   future
版权声明:   本博客所有文章除特別声明外,均采用 CC BY 4.0 许可协议。转载请注明来源 future !
 上一篇
404. 左叶子之和 404. 左叶子之和
404. 左叶子之和难度简单 286计算给定二叉树的所有左叶子之和。示例:    3   /   9  20    /      15   7 在这个二叉树中,有两个左叶子,分别是 9 和 15,所以返回 24. 一个节点为「左叶子」节点,
2021-03-01 future
下一篇 
257. 二叉树的所有路径 257. 二叉树的所有路径
257. 二叉树的所有路径难度简单 454给定一个二叉树,返回所有从根节点到叶子节点的路径。说明: 叶子节点是指没有子节点的节点。示例:输入: 1 /   2     3   5 输出: [“1->2->5”, “1->3
2021-03-01 future
  目录