LeetCode125——驗證回文串

我的LeetCode代碼倉：https://github.com/617076674/LeetCode

原題連結：https://leetcode-cn.com/problems/valid-palindrome/description/

題目描述：

知識點：字元串、雙指針

思路一：先過濾去非字母和非數字字元

時間複雜度和空間複雜度均是O(n)，其中n為輸入字元串的長度。

JAVA代碼：

public class Solution {
    public boolean isPalindrome(String s) {
        s = s.toLowerCase();
        StringBuilder stringBuilder = new StringBuilder();
        for(int i = 0; i < s.length(); i++){
            if(s.charAt(i) >= 'a' && s.charAt(i) <= 'z'){
                stringBuilder.append(s.charAt(i));
            }else if(s.charAt(i) >= '0' && s.charAt(i) <= '9'){
                stringBuilder.append(s.charAt(i));
            }
        }
        for(int i = 0; i < stringBuilder.length(); i++){
            if(stringBuilder.charAt(i) != stringBuilder.charAt(stringBuilder.length() - 1 - i)){
                return false;
            }
        }
        return true;
    }
}
           

LeetCode解題報告：

思路二：左右雙指針判斷，跳過非字母和非數字字元

時間複雜度是O(n)，其中n為輸入字元串的長度。空間複雜度是O(1)。

JAVA代碼：

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

    private boolean isLetterOrNumber(char c){
        if(c >= 'a' && c <= 'z'){
            return true;
        }else if(c >= '0' && c <= '9'){
            return true;
        }
        return false;
    }
}
           

LeetCode解題報告：