每日一道算法题LeetCode125:Valid Palindrome(验证回文串)
程序员文章站
2022-03-20 11:38:56
...
题目
给定一个字符串,验证它是否是回文串,只考虑字母和数字字符,可以忽略字母的大小写。
说明:本题中,我们将空字符串定义为有效的回文串。
分析
这道题并不难,很容易想到解法,需要注意的是只考虑字母和数组字符。空格,标点都不用考虑
题解
双指针
分别用两个指针,一个从前往后,一个从后往前,依次比较
public static boolean isPalindrome(String s) {
if (s == null || s.length() == 0)
return true;
s = s.toLowerCase(); // 全部转换为小写
for (int i = 0, j = s.length() - 1; i < j; i++, j--) {
while (i < j && !Character.isLetterOrDigit(s.charAt(i))) // 只考虑字母或数字
i++;
while (i < j && !Character.isLetterOrDigit(s.charAt(j)))
j--;
if (s.charAt(i) != s.charAt(j))
return false;
}
return true;
}
正则+reverse
先使用正则将其他的字符去掉,然后直接比较源字符串与翻转字符串
public boolean isPalindrome(String s) {
String actual = s.replaceAll("[^A-Za-z0-9]", "").toLowerCase(); // 用正则将其他字符去除
String rev = new StringBuffer(actual).reverse().toString();
return actual.equals(rev); // 与翻转字符串比较
}
总结
简单题