剑指offer

剑指offer019-最多删除一个字符得到回文

最多删除一个字符得到回文

Posted by 高明 on 2020-01-01

剑指offer019-最多删除一个字符得到回文

题目

给定一个非空字符串 s，请判断如果 最多 从字符串中删除一个字符能否得到一个回文字符串。

 

示例 1:

输入: s = "aba"
输出: true

示例 2:

输入: s = "abca"
输出: true
解释: 可以删除 "c" 字符 或者 "b" 字符

示例 3:

输入: s = "abc"
输出: false

 

提示:

  • 1 <= s.length <= 105
  • s 由小写英文字母组成

 

注意：本题与主站 680 题相同： https://leetcode-cn.com/problems/valid-palindrome-ii/

Related Topics
  • 贪心
  • 双指针
  • 字符串

  • 👍 13
  • 👎 0

    • 思路

    首先就是如果这个字符串本身就是回文，就不需要改动

    先实现一个函数，用于判断字符串是否是回文，这个方法有很多，左右指针等，但是这里采用了代码编写上最简单的

    1
    2
    3
    4
    5
    6
    7
    private boolean isHui(String s) {
        StringBuilder sb = new StringBuilder(s);
        if (sb.toString().equals(sb.reverse().toString())) {
            return true;
        }
        return false;
    }
    1
    2
    3
    if (isHui(s)) {
        return true;
    }

    如果s不是回文，那么就一定会删除一个字符

    这个字符一开始我想着从中心往外面，碰到不一致的，就删除左边或者右边，发现这样不行，因为删除一个字符会导致回文的中心变动

    所以应该从两边往中心走，如果left==right，说明是没有问题的，一旦left！=right，这时候就需要考虑删除左边的还是右边的。当删除左或者删除右有一个能成为回文，则是回文，否则不是

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    int right = n - 1;
    for (int i = 0; i < n / 2; i++) {
        if (s.charAt(i) == s.charAt(right)) {
            right -= 1;
            continue;
        } else {
            // 删除left
            // 或者删除right
            return isHui(s.substring(i + 1, right + 1)) || isHui(s.substring(i, right));
        }
    }

    最后，当s的长度n是1，2时，必定是回文

    1
    2
    3
    4
    int n = s.length();
    if (n == 1 || n == 2) {
        return true;
    }

    代码

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    31
    32
    33
    class Solution {
        public boolean validPalindrome(String s) {
            int n = s.length();
            if (n == 1 || n == 2) {
                return true;
            }

            if (isHui(s)) {
                return true;
            }

            int right = n - 1;
            for (int i = 0; i < n / 2; i++) {
                if (s.charAt(i) == s.charAt(right)) {
                    right -= 1;
                    continue;
                } else {
                    // 删除left
                    // 或者删除right
                    return isHui(s.substring(i + 1, right + 1)) || isHui(s.substring(i, right));
                }
            }
            return true;
        }

        private boolean isHui(String s) {
            StringBuilder sb = new StringBuilder(s);
            if (sb.toString().equals(sb.reverse().toString())) {
                return true;
            }
            return false;
        }
    }
    1
    2
    3
    解答成功:
    执行耗时:9 ms,击败了12.05% 的Java用户
    内存消耗:39.1 MB,击败了10.47% 的Java用户

    优化一下回文的判断逻辑

    1
    2
    3
    4
    5
    6
    7
    8
    9
    private boolean isHui(String s) {
        int n = s.length();
        for (int i = 0; i < n / 2; i++) {
            if (s.charAt(i) != s.charAt(n - i - 1)) {
                return false;
            }
        }
        return true;
    }
    1
    2
    3
    解答成功:
    执行耗时:7 ms,击败了42.86% 的Java用户
    内存消耗:38.9 MB,击败了47.98% 的Java用户
    FEATURED TAGS
    剑指offer
    FRIENDS