|
Books are the bees which carry the quickening pollen from one to another mind.
书籍是蜜蜂，将花粉从一个头脑传到另一个头脑。 给定一个字符串，验证它是否是回文串，只考虑字母和数字字符，可以忽略字母的大小写。 说明：本题中，我们将空字符串定义为有效的回文串。 示例 1: 输入: "A man, a plan, a canal: Panama" 输出: true
示例 2: 输入: "race a car" 输出: false
“回文串”是一个正读和反读都一样的字符串，也就是说他是左右两边对称的。验证一个字符串是否是回文串，最简单的一种方式就是使用两个指针，一个从前开始，一个从后开始，两个指针同时往中间走，如果他们指向的字符不一样，那么这个字符串肯定不是回文字符串，直接返回false即可，如果这两个指针相遇了，直接返回true。
但这题只需要判断字母和数字，因为字符串中可能含有其他字符，我们只需要跳过即可，画个图来看下 
最后再来看下代码
1public boolean isPalindrome(String s) {
2 int left = 0, right = s.length() - 1;
3 while (left < right) {
4 //left是左指针，如果不是字母和数字要过滤掉
5 while (left < right && !Character.isLetterOrDigit(s.charAt(left)))
6 left++;
7 //right也一样，如果不是字母和数字也要过滤掉
8 while (left < right && !Character.isLetterOrDigit(s.charAt(right)))
9 right--;
10 //然后判断这两个字符是否相同，如果不相同直接返回false，这里是先把字符全部转化为小写
11 if (Character.toLowerCase(s.charAt(left)) != Character.toLowerCase(s.charAt(right)))
12 return false;
13 //如果left和right指向的字符忽略大小写相等的话，这两个指针要分别往中间移一步
14 left++;
15 right--;
16 }
17 //如果都比较完了，说明是回文串，返回true
18 return true;
19}
我们还可以在比较之前字母全部转化为小写，这里改为for循环的方式，只不过是换汤不换药，原理还都是一样的，来看一下 1public boolean isPalindrome(String s) {
2 //先转为小写
3 s = s.toLowerCase();
4 for (int i = 0, j = s.length() - 1; i < j; i++, j--) {
5 while (i < j && !Character.isLetterOrDigit(s.charAt(i)))
6 i++;
7 while (i < j && !Character.isLetterOrDigit(s.charAt(j)))
8 j--;
9 if (s.charAt(i) != s.charAt(j))
10 return false;
11 }
12 return true;
13}
上面代码还可以写成递归的方式，无论怎么变，核心思路还是没变，可以参考一下，代码如下
1public boolean isPalindrome(String s) {
2 return isPalindromeHelper(s, 0, s.length() - 1);
3}
4
5public boolean isPalindromeHelper(String s, int left, int right) {
6 if (left >= right)
7 return true;
8 while (left < right && !Character.isLetterOrDigit(s.charAt(left)))
9 left++;
10 while (left < right && !Character.isLetterOrDigit(s.charAt(right)))
11 right--;
12 return Character.toLowerCase(s.charAt(left)) == Character.toLowerCase(s.charAt(right))
13 && isPalindromeHelper(s, ++left, --right);
14}
回文字符串的判断，和冒泡排序一样算是比较简单的一道算法题，基本上没什么难度。
|
