欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

LeetCode125. Valid Palindrome

程序员文章站 2024-03-06 21:38:14
...

125.Valid Palindrome

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

For example,
“A man, a plan, a canal: Panama” is a palindrome.
“race a car” is not a palindrome.

Note:
Have you consider that the string might be empty? This is a good question to ask during an interview.

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

方法一:超时

public boolean isPalindrome(String s) {
    if(s.length() == 0) return true;      
    List<Character> a = new ArrayList<>();
    List<Character> b = new ArrayList<>();
    for(int i = 0; i < s.length(); i++){
        if(s.charAt(i) >= 'a' && s.charAt(i) <= 'z' ||s.charAt(i) >= 'A' && s.charAt(i) <= 'Z'|| s.charAt(i) >= '0' && s.charAt(i) <= '9'){
            a.add(s.charAt(i));
        }
    }
    for(int i = 0; i < a.size(); i++){
        b.add(0, a.get(i));
    }       
    if(String.valueOf(a).equalsIgnoreCase(String.valueOf(b))){
        return true;
    }   
    return false;
}

方法二:
设置一首一尾两个指针,每次比较两个指针指向的字符是否相等,若相等,则首指针向后移一个位置,尾指针向前移一个位置。

public boolean isPalindrome2(String s) {
    if (s.isEmpty()) {
        return true;
    }
    int head = 0, tail = s.length() - 1;
    char cHead, cTail;
    while(head <= tail) {
        cHead = s.charAt(head);
        cTail = s.charAt(tail);
        if (!Character.isLetterOrDigit(cHead)) {
            head++;
        } else if(!Character.isLetterOrDigit(cTail)) {
            tail--;
        } else {
            if (Character.toLowerCase(cHead) != Character.toLowerCase(cTail)) {
                return false;
            }
            head++;
            tail--;
        }
    }
    return true;
}

方法三:
这个方法用到了正则表达式,并用到了StringBuffer类自带的reverse函数。

public boolean isPalindrome3(String s) {
    String actual = s.replaceAll("[^A-Za-z0-9]", "").toLowerCase();
    String rev = new StringBuffer(actual).reverse().toString();
    return actual.equals(rev);
}

注意:
字符串比较应该用equals()方法,不能用 == 号。

相关标签: string leetcode