[刷题班] LeetCode125. 验证回文串

题目描述

思路：左右指针

只考虑数字和字母
字母的话需要全部转化为小写
然后使用左右指针判断是否是回文串

方法一：

class Solution {
    public boolean isPalindrome(String s) {
        List<Character> list = new ArrayList<>();
        for (char c : s.toCharArray()) {
            if (c >= 'A' && c <= 'Z') {
                list.add((char)(c + 32));
            } else if (c >= 'a' && c <= 'z') {
                list.add(c);
            } else if (c >= '0' && c <= '9') {
                list.add(c);
            }       
        } 
        int size = list.size() - 1;
        // 左右指针
        for (int left = 0, right = size; left < right; left ++, right --) {
            if (list.get(left) != list.get(right)) {
                return false;
            }
        }
        return true;
    }
}

时间复杂度：O(n)、空间复杂度：O(n)

方法二：

class Solution {
    public boolean isPalindrome(String s) {
        int left = 0, right = s.length() - 1;
        while (left < right) {
            // 忽略left左边无效字符,在数字和字母字符停下
            while (left < right && !Character.isLetterOrDigit(s.charAt(left))) {
                left ++;
            }
            // 忽略right右边无效字符
            while (left < right && !Character.isLetterOrDigit(s.charAt(right))) {
                right --;
            }

            if (left < right) {
                if (Character.toLowerCase(s.charAt(left)) != Character.toLowerCase(s.charAt(right))) {
                    return false;
                }
                left ++;
                right --;
            }
        }
        return true;
    }
}

时间复杂度：O(n)、空间复杂度：O(1)

Character.isLetterOrDigit()：判断是否是字母或者数字
Character.toLowerCase()：转小写

Character.toLowerCase(char ch) 方法用于将指定的字符参数转换为小写。对于数字字符，它不会有任何影响，即数字字符保持不变。这是因为数字字符在小写和大写之间没有大小写之分。