1. 代码段小站首页
  2. 算法

leetcode680-验证回文字符串II

彭晨涛 • • 算法 • 阅读 18

原题

给定一个非空字符串 s，最多删除一个字符。判断是否能成为回文字符串。

示例 1:

输入: "aba"
输出: True

示例 2:

输入: "abca"
输出: True
解释: 你可以删除c字符。

注意:

  1. 字符串只包含从 a-z 的小写字母。字符串的最大长度是50000。

解法

思想

双指针，当遇到左右两个字符不等的时候，删除左边的，再继续判断是否相等，或删除右边的，再继续判断是否相等。

代码

class Solution {
    public boolean validPalindrome(String s) {
        int p1 = 0,p2 = s.length()-1;
        while(p1<=p2){
            if(s.charAt(p1)!= s.charAt(p2)){
                String reverse = new StringBuilder(s).reverse().toString();
                return s.substring(p1+1,p2+1).equals(reverse.substring(p1,p2)) || s.substring(p1,p2).equals(reverse.substring(p1+1,p2+1));
            }
            p1++;p2--;
        }
        return true;
    }
}

原创文章，作者：彭晨涛，如若转载，请注明出处：https://www.codetool.top/article/leetcode680-%e9%aa%8c%e8%af%81%e5%9b%9e%e6%96%87%e5%ad%97%e7%ac%a6%e4%b8%b2ii/

赞 (0)
彭晨涛彭晨涛管理者
0 0
上一篇 2020年5月18日 16:06
下一篇 2020年5月19日 15:23

相关推荐

  • leetcode295-数据流的中位数

    原题 中位数是有序列表中间的数。如果列表长度是偶数，中位数则是中间两个数的平均值。 例如， [2,3,4] 的中位数是 3 [2,3] 的中位数是 (2 + 3) / 2 = 2....

    彭晨涛 彭晨涛
    算法 2020年2月12日
    050

  • leetcode74-搜索二维矩阵

    原题 编写一个高效的算法来判断 m x n 矩阵中，是否存在一个目标值。该矩阵具有如下特性： 每行中的整数从左到右按升序排列。 每行的第一个整数大于前一行的最后一个整数。   示例...

    彭晨涛 彭晨涛
    算法 2020年4月29日
    0100

  • leetcode1413-逐步求和得到正数的最小值

    原题 给你一个整数数组 nums 。你可以选定任意的 正数 startValue 作为初始值。 你需要从左到右遍历 nums 数组，并将 startValue 依次累加上 nums...

    彭晨涛 彭晨涛
    算法 2020年6月21日
    02140

  • leetcode341-扁平化嵌套列表迭代器

    原题 给定一个嵌套的整型列表。设计一个迭代器，使其能够遍历这个整型列表中的所有整数。 列表中的项或者为一个整数，或者是另一个列表。 示例1： 输入: [[1,1],2,[1,1]]...

    彭晨涛 彭晨涛
    算法 2020年1月27日
    050
  • leetcode234-回文链表 算法

    leetcode234-回文链表

    原题 请判断一个链表是否为回文链表。 示例1： 输入： 1->2 输出： false 示例2： 输入： 1->2->2->1 输出： true 进阶: 你能否用 O(n) 时间复杂...

    彭晨涛 彭晨涛
    2019年12月16日
    080

  • leetcode80-删除排序数组中的重复项II

    原题 给定一个排序数组，你需要在原地删除重复出现的元素，使得每个元素最多出现两次，返回移除后数组的新长度。 不要使用额外的数组空间，你必须在原地修改输入数组并在使用 O(1) 额外...

    彭晨涛 彭晨涛
    算法 2020年5月26日
    0110

  • leetcode121-买卖股票的最佳时机

    原题 给定一个数组，它的第 i 个元素是一支给定股票第 i 天的价格。 如果你最多只允许完成一笔交易（即买入和卖出一支股票），设计一个算法来计算你所能获取的最大利润。 注意你不能在...

    彭晨涛 彭晨涛
    算法 2020年3月9日
    080

  • leetcode66-加一

    原题 给定一个由整数组成的非空数组所表示的非负整数，在该数的基础上加一。 最高位数字存放在数组的首位， 数组中每个元素只存储单个数字。 你可以假设除了整数 0 之外，这个整数不会以...

    彭晨涛 彭晨涛
    算法 2019年11月14日
    0130
  • leetcode150-逆波兰表达式求值 算法

    leetcode150-逆波兰表达式求值

    原题 根据逆波兰表示法，求表达式的值。 有效的运算符包括 +, -, *, / 。每个运算对象可以是整数，也可以是另一个逆波兰表达式。 说明： 整数除法只保留整数部分。 给定逆波兰...

    彭晨涛 彭晨涛
    2019年12月12日
    060

  • leetcode700-二叉搜索树中的搜索

    原题 给定二叉搜索树（BST）的根节点和一个值。 你需要在BST中找到节点值等于给定值的节点。 返回以该节点为根的子树。 如果节点不存在，则返回 NULL。 例如， 给定二叉搜索树...

    彭晨涛 彭晨涛
    算法 2020年1月16日
    070

发表回复

登录后才能评论