题目描述

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

  1. 输入: s = "aba"
  2. 输出: true
  1. 输入: s = "abca"
  2. 输出: true
  3. 解释: 可以删除 "c" 字符 或者 "b" 字符
  1. 输入: s = "abc"
  2. 输出: false

提示:

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

    解题思路

    最多删除一个字符，这要考虑两种情况，
    一是删除左失配字符，二是删除右失配字符
    因此要给两次机会

    实现代码

    1. public boolean validPalindrome(String s) {
    2.   int count = 2;
    3.   // 双指针
    4.   int i = 0;
    5.   int j = s.length() - 1;
    6.   // 记忆i,j失配的位置,便于回溯
    7.   int memi = 0;
    8.   int memj = 0;
    9.   while (i < j) {
    10.       if (s.charAt(i) != s.charAt(j)) {
    11.           if (count == 2) {
    12.           // 先尝试删除左边
    13.               count--;
    14.               memi = i++;
    15.               memj = j;
    16.               continue;
    17.           }else if (count == 1) {
    18.           // 尝试删除右边
    19.               count--;
    20.               i = memi;
    21.               j = --memj;
    22.               continue;
    23.           }else {
    24.               return false;
    25.           }
    26.       }
    27.       i++;
    28.       j--;
    29.   }
    30.   return true;
    31. }

    时间及空间复杂度分析

    时间O(n)
    空间O(1)
    image.png

    拓展思路