Leetcode-125-验证回文串

Leecode-125-Valid Palindrome

思路：双指针

题目描述

给定一个字符串，验证它是否是回文串，

• 只考虑字母和数字字符， (Character.isLettorOrDigit())
• 可以忽略字母的大小写。（toLowerCase()）

输入: "A man, a plan, a canal: Panama"
输出: true


输入: "race a car"
输出: false

Solution：

• 左右指针遍历字符串

• 左指针不是字符或者数字（向右移动一位，结束本次循环）

• 右指针不是字符或者数字（向左移动一位，结束本次循环）

• 左右对应字母或者数字相等（同时移动一位，继续判断下一位是否相等）

Java

Solution :

// 双指针
class Solution {
    public boolean isPalindrome(String s) {
        // 空字符串也是回文串
        if (s.length() == 0){
            return true;
        }

        // 全部转化成小写比较
        String low = s.toLowerCase();

        int left  = 0;
        int right = s.length() - 1;

        while (left < right){
            // 如果左指针不是数字或者字母
            if (!Character.isLetterOrDigit(low.charAt(left))){
                left++;
                continue;
            }

            // 如果右指针不是数字或者字母
            if (!Character.isLetterOrDigit(low.charAt(right))){
                right--;
                continue;
            }

            // 如果两个指针不相等
            if (low.charAt(left) != low.charAt(right)){
                return false;
            }else {
                left++;
                right--;
            }
        }
        return true;
    }
}

• 时间复杂度： O(n) 遍历一遍字符串
• 空间复杂度： O(1) 不需要额外的空间

测试用例：race a car

public static void main(String[] args) {
    Solution solution = new Solution();
    System.out.println(solution.isPalindrome("race a car"));
}

打赏