我的书签
添加书签
移除书签题目描述（简单难度）
判断一个字符串是否是回文串，忽略掉除了字母和数字外的字符。
解法一
两个指针，一个指针从头进行，一个指针从尾部进行。依次判断两个指针的字符是否相等，同时要跳过非法字符。需要注意的是，两个指针不用从头到尾遍历，当两个指针相遇的时候就意味着这个字符串是回文串了。
还需要注意的是 'A' == 'a' ，也就是大写字母和小写字母是相同的。
1. public boolean isPalindrome(String s) {
2. int len = s.length();
3. s = s.toLowerCase(); //统一转为小写
4. int i = 0, j = len - 1;
5. while (i < j) {
6. //跳过非法字符
7. while (!isAlphanumeric(s.charAt(i))) {
8. i++;
9. //匹配 " " 这样的空白字符串防止越界
10. if (i == len) {
11. return true;
12. }
13. }
14. while (!isAlphanumeric(s.charAt(j))) {
15. j--;
16. }
17. if (s.charAt(i) != s.charAt(j)) {
18. return false;
19. }
20. i++;
21. j--;
22. }
23. return true;
24. }
25. 26. private boolean isAlphanumeric(char c) {
27. if ('a' <= c && c <= 'z' || 'A' <= c && c <= 'Z' || '0' <= c && c <= '9') {
28. return true;
29. }
30. return false;
31. }
解法二
上边的是常规的思路，这里分享另一个 思路>) 。
上边为了处理大小写字母的问题，首先全部统一为了小写。为了找出非法字符，每次都需要判断一下该字符是否在合法范围内。
这里用一个技巧，把 '0' 到 '9' 映射到 1 到 10，'a' 到 'z' 映射到 11 到 36 ，'A' 到 'Z' 也映射到 11 到 36 。然后把所有数字和字母用一个 char 数组存起来，没存的字符就默认映射到 0 了。
这样只需要判断字符串中每个字母映射过去的数字是否相等，如果是 0 就意味着它是非法字符。
1. private static final char[] charMap = new char[256];
2. 3. static {
4. // 映射 '0' 到 '9'
5. for (int i = 0; i < 10; i++) {
6. charMap[i + '0'] = (char) (1 + i); // numeric
7. }
8. // 映射 'a' 到 'z' 和 映射 'A' 到 'Z'
9. for (int i = 0; i < 26; i++) {
10. charMap[i + 'a'] = charMap[i + 'A'] = (char) (11 + i);
11. }
12. }
13. 14. public boolean isPalindrome(String s) {
15. char[] pChars = s.toCharArray();
16. int start = 0, end = pChars.length - 1;
17. char cS, cE;
18. while (start < end) {
19. // 得到映射后的数字
20. cS = charMap[pChars[start]];
21. cE = charMap[pChars[end]];
22. if (cS != 0 && cE != 0) {
23. if (cS != cE)
24. return false;
25. start++;
26. end--;
27. } else {
28. if (cS == 0)
29. start++;
30. if (cE == 0)
31. end--;
32. }
33. }
34. return true;
35. }
总
很简单的一道题了，值得注意的就是解法二将所有字母进行映射，同时将大小写字母映射到同一个数字的想法，省了很多事，速度会提升一些。也可以做一下 第 5 题 ，给定一个字符串，找出最长的回文子串，里边的介绍的马拉车算法是真的太强了。
添加好友一起进步~
如果觉得有帮助的话，可以点击 这里 给一个 star 哦 ^^
如果想系统的学习数据结构和算法，强烈推荐一个我之前学过的课程，可以点击 这里 查看详情
