.asp网站开发,东莞市领导班子,兼职 网站建设,网站建设费用设计题目链接 剑指 Offer II 019. 最多删除一个字符得到回文 easy 题目描述
给定一个非空字符串 s#xff0c;请判断如果 最多 从字符串中删除一个字符能否得到一个回文字符串。
示例 1: 输入: s “aba” 输出: true 示例 2: 输入: s “abca” 输出: true 解释: 可以删除 “c”…题目链接 剑指 Offer II 019. 最多删除一个字符得到回文 easy 题目描述
给定一个非空字符串 s请判断如果 最多 从字符串中删除一个字符能否得到一个回文字符串。
示例 1: 输入: s “aba” 输出: true 示例 2: 输入: s “abca” 输出: true 解释: 可以删除 “c” 字符 或者 “b” 字符 示例 3: 输入: s “abc” 输出: false 提示
1s.length1051 s.length 10^51s.length105s由小写英文字母组成
分析
因为要求 最多删除一个字符能否构成回文串。
当 s[i] s[j]那么直接缩减范围 i , j--当 s[i] ! s[j]直接判断 s[i1,j]或者 s[i,j-1]是否为回文串即可相当于删除了一个字符
时间复杂度 O(n)O(n)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(i1,j,s) || check(i,j-1,s);}}return true;}
}
