剑指 Offer II 019. 最多删除一个字符得到回文

题目链接

剑指 Offer II 019. 最多删除一个字符得到回文 easy

题目描述

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

示例 1:

输入: s = “aba”
输出: true

示例 2:

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

示例 3:

输入: s = “abc”
输出: false

提示：

• $1<=s.length<=10^5$
• s由小写英文字母组成

分析：

因为要求 最多删除一个字符，能否构成回文串。

• 当 s[i] == s[j]，那么直接缩减范围 i++ , j--
• 当 s[i] != s[j]，直接判断 s[i+1,j]或者 s[i,j-1]是否为回文串即可（相当于删除了一个字符）

时间复杂度： $O(n)$

C++代码：

class Solution {
public:bool check(int l,int r,string &s){for(int i = l,j = r;i < j;i++,j--){if(s[i] != s[j]) return false;}return true;}bool validPalindrome(string s) {int n = s.size();for(int i = 0,j = n - 1;i < j;){if(s[i] == s[j]){i++;j--;}else{return check(i + 1,j,s) || check(i,j-1,s);}}return true;}
};

Java代码：

class Solution {private boolean check(int l,int r,String s){for(int i = l,j = r;i < j;i++,j--){if(s.charAt(i) != s.charAt(j)) return false;}return true;}public boolean validPalindrome(String s) {int n = s.length();for(int i = 0,j = n - 1;i < j;){if(s.charAt(i) == s.charAt(j)){i++;j--;}else{return check(i+1,j,s) || check(i,j-1,s);}}return true;}
}