LeetCode 125. Valid Palindrome [Easy]

发表于 | 更新于 | 分类于 ， | 阅读次数：

题目来源：https://leetcode.com/problems/valid-palindrome/

题目难度：Easy

题目

Given a string, determine if it is a palindrome, considering only alphanumeric characters and ignoring cases.

Note: For the purpose of this problem, we define empty string as valid palindrome.

Example 1:

1
2
Input: "A man, a plan, a canal: Panama"
Output: true

Example 2:

1
2
Input: "race a car"
Output: false

分析

只考虑字母和数字。忽略大小写。

解答1[Java]：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
class Solution {
    public boolean isPalindrome(String s) {
        char[] charMap = new char[256];
        for (int i = 0; i < 10; i++) {
            // numeric - don't use 0 as it's reserved for illegal chars
            charMap['0' + i] = (char) (1 + i);
        }
        for (int i = 0; i < 26; i++) {
            //alphabetic, ignore cases, continue from 11
            charMap['a' + i] = charMap['A' + i] = (char) (11 + i);
        }

        for (int start = 0, end = s.length() - 1; start < end; ) {
            if (charMap[s.charAt(start)] == 0) {
                start++;
            } else if (charMap[s.charAt(end)] == 0) {
                end--;
            } else if (charMap[s.charAt(start++)] != charMap[s.charAt(end--)]) {
                return false;
            }
        }
        return true;
    }
}

思路

先打一个表。

注意：通过 charMap['A'] 这种方式访问数组元素的时候，Java 会自动把 [] 中的字符转换为 int 型。

解答2[Java]：

1
2
3
4
5
6
7
public class Solution {
    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);
    }
}

使用正则表达式和 Java 的类库。先把所有字母都转换成小写，反转字符串然后对比。

其他

发现 Java 的连等赋值好像比非连等赋值性能要更好一些。