ARTS打卡：第十七周

每周完成一个ARTS：

Algorithm：每周至少做一个 leetcode 的算法题

Review：阅读并点评至少一篇英文技术文章

Tip：学习至少一个技术技巧

Share：分享一篇有观点和思考的技术文章

Algorithm

125. 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:

Input: “A man, a plan, a canal: Panama”
Output: true

Example 2:

Input: “race a car”
Output: false

@DevDocsleetcode.com/problems/valid-anagram

题意

给定一个字符串，判断它是否是回文，只考虑字母数字字符且忽略大小写。

注意：为了解决这个问题，我们将空字符串定义为有效的回文。

解题思路（1）

这题很简单，根据题意，得出以下两个限制条件：

只考虑字母数字字符且忽略大小写
将空字符串定义为有效的回文

那么解法就显而易见了：

通过正则表达式过滤掉除字母数字之外的字符，并将字母全部转为小写字母
将字符串翻转后，进行比较即可

代码实现（1）

class Solution {
    public boolean isPalindrome(String s){
        // 通过正则过滤掉除字母数字之外的字符，并将字母全部转为小写字母
        String s1 = s.replaceAll("[^A-Za-z0-9]", "").toLowerCase();
        // 利用 StringBuilder#reverse() API 翻转字符串
        String s2 = new StringBuilder(s1).reverse().toString();
        // 比较两个字符串
        return s1.equals(s2);
    }
}

运行结果和复杂度分析（1）

运行结果：

Runtime: 18 ms, faster than 23.43% of Java online submissions for Valid Palindrome.

Memory Usage: 37.8 MB, less than 96.94% of Java online submissions for Valid Palindrome.

复杂度分析：

暂未清楚如何分析….🕊

解题思路（2）

借鉴散列表的思想，换一个解题角度出发（嘿嘿嘿，是不是发现跟上周的解题思路类似呢😜）：

ASCII 码表加上拓展集共256个字符，所以我们可以定义一个长度为256的整形数组来模拟散列表，下标为字符的值，数组的值用于标识字符。
字母或数字字符对应数组存储的值，是唯一的，其余字符皆为0，这样就不用过滤除字母或数字之外的字符了。
头尾指针遍历比较

结合代码，更容易理解哟(＾Ｕ＾)ノ~ＹＯ

代码实现（2）

class Solution{
    // 定义一个长度为256的整形数组来模拟散列表，下标为字符的值，数组的值用于标识字符(ASCII 码表加上拓展集共256个字符)。
    private static final int[] map = new int[256];

    // 初始化整形数组，字母或数字字符对应数组存储的值，要唯一的，其余字符皆为0，这样就不用过滤除字母或数字之外的字符了。
    static {
        for (int i = 0; i < 10; i++) {
            // 初始化数字字符的值，+ 1 是为了值不出现 0
            map[i + '0'] = i + 1;
        }
        for (int i = 0; i < 26; i++) {
            // 初始化字母的值，并做大小写忽略处理，值相同即可
            map[i + 'a'] = map[i + 'A'] = 11 + i;
        }
    }

    public boolean isPalindrome(String s) {
        // 换成字符数组
        char[] pChars = s.toCharArray();
        // 头尾指针
        int start = 0, end = pChars.length - 1;
        // sV 头指针指向的值，eV 尾指针指向的值
        int sV, eV;
        while (start < end) {
            sV = map[pChars[start]];
            eV = map[pChars[end]];
            // sV != 0 代表 pChars[start] 是字母或数字字符
            if (sV != 0 && eV != 0) {
                // 值不相同，pChars[start] ！= pChars[end] 即字符不同
                if (sV != eV) {
                    return false;
                }
                start++;
                end--;
            } else {
                // 如果头指针指向的字符是字母或数字字符之外的字符，则往前移动头指针
                if (sV == 0) {
                    start++;
                }
                // 如果尾指针指向的字符是字母或数字字符之外的字符，则往后移动尾指针
                if (eV == 0) {
                    end--;
                }
            }
        }
        return true;

    }
}