讨论/《算法面试题汇总》 - 验证回文串/
《算法面试题汇总》 - 验证回文串
共 15 个回复

1,双指针解决

这题没什么难度,最简单的就是使用双指针,一个指向前,一个指向后,遇到空格以及特殊字符要跳过,然后判断,画个图来看下
image.png

    public boolean isPalindrome(String s) {
        if (s.length() == 0)
            return true;
        int left = 0, right = s.length() - 1;
        while (left < right) {
            //因为题中说了,只考虑字母和数字,所以不是字母和数字的先过滤掉
            while (left < right && !Character.isLetterOrDigit(s.charAt(left)))
                left++;
            while (left < right && !Character.isLetterOrDigit(s.charAt(right)))
                right--;
            //然后把两个字符变为小写,在判断是否一样,如果不一样,直接返回false
            if (Character.toLowerCase(s.charAt(left)) != Character.toLowerCase(s.charAt(right)))
                return false;
            left++;
            right--;
        }
        return true;
    }


2,双指针的另一种写法

我们还可以在比较之前字母全部转化为小写,这里改为for循环的方式,只不过是换汤不换药,原理还都是一样的

    public boolean isPalindrome(String s) {
        if (s == null || s.length() == 0)
            return true;
        s = s.toLowerCase();
        for (int i = 0, j = s.length() - 1; i < j; i++, j--) {
            while (i < j && !Character.isLetterOrDigit(s.charAt(i)))
                i++;
            while (i < j && !Character.isLetterOrDigit(s.charAt(j)))
                j--;
            if (s.charAt(i) != s.charAt(j))
                return false;
        }
        return true;
    }


3,使用正则匹配

这题还可以使用正则匹配,把特殊字符过滤掉,只留下字母和数字,然后转化为小写,再反转,最后在判断是否相等。

    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);
    }


4,递归方式实现

如果想玩出花样,我们还可以把第一种的解题思路改为递归的方式

    public boolean isPalindrome(String s) {
        return isPalindromeHelper(s, 0, s.length() - 1);
    }

    public boolean isPalindromeHelper(String s, int left, int right) {
        if (left >= right)
            return true;
        while (left < right && !Character.isLetterOrDigit(s.charAt(left)))
            left++;
        while (left < right && !Character.isLetterOrDigit(s.charAt(right)))
            right--;
        return Character.toLowerCase(s.charAt(left)) == Character.toLowerCase(s.charAt(right)) && isPalindromeHelper(s, ++left, --right);
    }


我把部分算法题整理成了PDF文档,截止目前总共有900多页,大家可以下载阅读
链接https://pan.baidu.com/s/1hjwK0ZeRxYGB8lIkbKuQgQ
提取码:6666

如果觉得有用就给个赞吧,还可以关注我的LeetCode主页查看更多的详细题解

4
var isPalindrome = function(s) {
    const str = s.replaceAll(/[^A-Za-z0-9]/g,'').toLowerCase();
    const str1 =[...str].reverse().join('');
    return str === str1
};
1

正则匹配方法, 评论区大佬的思路, python版实现

class Solution:
    def isPalindrome(self, s: str) -> bool:
        s = s.lower()
        s1 = re.findall(r'[a-z0-9]', s)
        s2 = "".join(s1)
        # 使用字符串切片反转
        return s2[::-1] == s2
1
/**
 * @param {string} s
 * @return {boolean}
 */
var isPalindrome = function (s) {
    let isValidElem = (s) => {
        let str = 'qwertyuioplkjhgfdsazxcvbnm1234567890QWERTYUIOPLKJHGFDSAZXCVBNM' //有效的字符
        return str.indexOf(s) > -1 //判断是否为有效字符
    }
    let stack = [] //存储有效字符串
    for (let i = 0; i < s.length; i++) {
        if (isValidElem(s[i])) {
            stack.push(s[i].toLocaleLowerCase()) //小写字母存储有效字符串
        }
    }
    let left = 0, right = stack.length - 1; //双指针
    while (left < right) {
        if (stack[left] !== stack[right]) return false
        left++ //左指针
        right-- //右指针
    }
    return true
};
class Solution(object):
    def isPalindrome(self, s):
        """
        :type s: str
        :rtype: bool
        """
        def isValidElem(self, s1): ##判断是否为有效字符串
            return '0' <= s1 <= '9' or 'a' <= s1 <= 'z' or 'A' <= s1 <= 'Z'

        stack = [] ## 存储有效字符串
        for i in range(len(s)):
            if isValidElem(self,s[i]):
                stack.append(s[i].lower()) ## 小写提出有效字符串

        left, right = 0, len(stack)-1 ## 双指针遍历
        while left < right:
            if stack[left] != stack[right]: ## 判断首尾是否相同
                return False
            left +=1
            right-=1
        return True
1

捕获.PNG

var isPalindrome = function(initStr) {
initStr=initStr.replace(/[^a-zA-Z0-9]/g,"").toLocaleLowerCase();
let reverStr=String([...initStr].reverse()).replace(/,/g,'');
return initStr==reverStr
};

class Solution {
public boolean isPalindrome(String s) {
if(s.length()==0) return true;
int left=0,right=s.length()-1;
while(left<right){
while(left<right && !Character.isLetterOrDigit(s.charAt(left))){
left++;
}
while(left<right && !Character.isLetterOrDigit(s.charAt(right))){
right--;
}
if(Character.toLowerCase(s.charAt(left)) != Character.toLowerCase(s.charAt(right))){
return false;
}
left++;
right--;
}
return true;
}
}

奇数也能通过啊,有不通过的测试案例吗

遇到奇数长度的字符串,你第一个算法是无法找到的

不调包

class Solution {
    public boolean isPalindrome(String s) {
        if (s.length() == 0 || s.length() == 1){
            return true;
        }
        int l = 0;
        int r = s.length()-1;

        while (l <= r ){
            if (!isValidChar(s.charAt(l))){
                l++;
                continue;
            }
            if (!isValidChar(s.charAt(r))){
                r--;
                continue;
            }

            if (!isCharEqual(s.charAt(l), s.charAt(r))){
                return false;
            }
            l++;
            r--;
        }
        return true;
    }

    private boolean isValidChar(char c){
        if ((c <= '9' && c >= '0') || (c >= 'a' && c <= 'z') || (c >= 'A' && c <= 'Z')){
            return true;
        }
        return false;
    }

    private boolean isCharEqual(char s, char d){
        if (s >= 'a'){
            s = (char) (s - 'a' + 'A');
        }
        if (d >= 'a'){
           d = (char) (d - 'a' + 'A');
        }

        if (s == d){
            return true;
        }

        return false;
    }
}