一边看覃超的斗鱼直播一遍写的：
- in place comparison: s[i] == s[n-i-1] ?
- reverse and compare
- stack, queue
对应第一种方法：
这题还可以直接用Character.isLetterOrDigit。
已犯错误：
- while里面少了 i<=s.length() - 1
public boolean isPalindrome(String s) {
if (s.length() < 2) return true;
int i = 0, j = s.length() - 1;
while (i < j) {
while (i<=s.length() - 1 && !isNumber(s.charAt(i)) && !isAlpha(s.charAt(i))) {
i++;
}
while (j>=0 && !isNumber(s.charAt(j)) && !isAlpha(s.charAt(j))) {
j--;
}
if (i >= j) return true;
if (isSame(s.charAt(i), s.charAt(j))) {
i++;
j--;
} else {
return false;
}
}
return true;
}
public boolean isNumber(char c) {
//要用单引号
if (c >= '0' && c <= '9') return true;
else return false;
}
public boolean isAlpha(char c) {
if (c >= 'a' && c <= 'z' || c >= 'A' && c <= 'Z') return true;
else return false;
}
public boolean isSame(char a, char b) {
if (isNumber(a) && isNumber(b)) {
return a == b;
} else if (Character.toLowerCase(a) == Character.toLowerCase(b)) return true;
else return false;
}
第二种方法
常规的排除干扰的Palindrome的写法，先用正则过滤掉非法字符，再用head和tail指针对比。其实跟第一种差不多。
public class ValidPalindrome {
public static boolean isValidPalindrome(String s){
if(s==null||s.length()==0) return false;
s = s.replaceAll("[^a-zA-Z0-9]", "").toLowerCase();
System.out.println(s);
for(int i = 0; i < s.length() ; i++){
if(s.charAt(i) != s.charAt(s.length() - 1 - i)){
return false;
}
}
return true;
}
public static void main(String[] args) {
String str = "A man, a plan, a canal: Panama";
System.out.println(isValidPalindrome(str));
}
}
第三种方法：
用Stack，同样先把用正则过滤。这个应该用手写一遍的。
public boolean isPalindrome(String s) {
s = s.replaceAll("[^a-zA-Z0-9]", "").toLowerCase();
int len = s.length();
if (len < 2)
return true;
Stack<Character> stack = new Stack<Character>();
int index = 0;
while (index < len / 2) {
stack.push(s.charAt(index));
index++;
}
if (len % 2 == 1)
index++;
while (index < len) {
if (stack.empty())
return false;
char temp = stack.pop();
if (s.charAt(index) != temp)
return false;
else
index++;
}
return true;
}
see :
http://www.programcreek.com/2013/01/leetcode-valid-palindrome-java/
