题目描述
分析
1. 暴力
时间复杂度:O(n^2) 两个指针指向数组的左右两侧，若有字符不相等的，则截取判断是否是回文串
特殊字符串：”eceec”，若按只去掉左侧字符判断是否是回文串，会有问题，所有添加了再按去掉右侧字符判断，两次判断有一个为真即可
代码实现
public enum Q680 {
instance;
public boolean validPalindrome(String s) {
if(s==null||s.length()==0) return false;
for(int i=0,j=s.length()-1;i<=j;i++,j--){
if(s.charAt(i)!=s.charAt(j)){
boolean a=false,b=false;
if(s.charAt(i)==s.charAt(j-1)){
a=isReverse(s.substring(i,j));
}
if(s.charAt(i+1)==s.charAt(j)){
b=isReverse(s.substring(i+1,j+1));
}
// if string is "eceec"
return a||b;
}
}
return true;
}
private boolean isReverse(String s){
for(int i=0,j=s.length()-1;i<=j;i++,j--){
if(s.charAt(i)!=s.charAt(j)){
return false;
}
}
return true;
}
public static void main(String[] args) {
// assert true
System.out.println(Q680.instance.validPalindrome("caba"));
// assert true
System.out.println(Q680.instance.validPalindrome("abccba"));
// assert true
System.out.println(Q680.instance.validPalindrome("abcecba"));
// assert true
System.out.println(Q680.instance.validPalindrome("abcecbae"));
// assert true
System.out.println(Q680.instance.validPalindrome("ebcbbececabbacecbbcbe"));
// assert true
System.out.println(Q680.instance.validPalindrome("eceec"));
}
}
