【经典算法】LeetCode 125. 验证回文串(Java/C/Python3实现含注释说明,Easy)

给定一个字符串，判断它是否是回文串，只考虑字母和数字字符，可以忽略字母的大小写。

public boolean isPalindrome(String s) {
    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;
}

#include <ctype.h>
#include <stdbool.h>
#include <string.h>
bool isPalindrome(char *s) {
    int left = 0, right = strlen(s) - 1;
    while (left < right) {
        // 跳过非字母和数字的字符
        while (left < right && !isalnum(s[left])) {
            left++;
        }
        while (left < right && !isalnum(s[right])) {
            right--;
        }
        // 转换为小写并比较
        if (tolower(s[left]) != tolower(s[right])) {
            return false;
        }
        left++;
        right--;
    }
    return true;
}

def isPalindrome(s: str) -> bool:
    left, right = 0, len(s) - 1
    while left < right:
        # 跳过非字母和数字的字符
        while left < right and not s[left].isalnum():
            left += 1
        while left < right and not s[right].isalnum():
            right -= 1
        # 转换为小写并比较
        if s[left].lower() != s[right].lower():
            return False
        left += 1
        right -= 1
    return True

func isPalindrome(s string) bool {
    left, right := 0, len(s)-1
    for left < right {
        // 跳过非字母和数字的字符
        for left < right && !isAlnum(s[left]) {
            left++
        }
        for left < right && !isAlnum(s[right]) {
            right--
        }
        // 转换为小写并比较
        if toLower(s[left]) != toLower(s[right]) {
            return false
        }
        left++
        right--
    }
    return true
}
func isAlnum(c byte) bool {
    return (c >= 'a' && c <= 'z') || (c >= 'A' && c <= 'Z') || (c >= '0' && c <= '9')
}
func toLower(c byte) byte {
    if c >= 'A' && c <= 'Z' {
        return c + 'a' - 'A'
    }
    return c
}

import java.util.Stack;
public boolean isPalindromeWithStack(String s) {
    Stack<Character> stack = new Stack<>();
    for (char c : s.toCharArray()) {
        if (Character.isLetterOrDigit(c)) {
            stack.push(Character.toLowerCase(c));
        }
    }
    
    for (char c : s.toCharArray()) {
        if (Character.isLetterOrDigit(c)) {
            char topChar = stack.pop();
            if (Character.toLowerCase(c) != topChar) {
                return false;
            }
        }
    }
    
    // 如果栈不为空，说明前半部分有多余字符，不是回文
    return stack.isEmpty();
}

#include <ctype.h>
#include <stdbool.h>
#define MAX_STACK_SIZE 1000
bool isPalindromeWithStack(char *s) {
    char stack[MAX_STACK_SIZE];
    int top = -1;
    
    for (int i = 0; s[i] != '\0'; i++) {
        if (isalnum(s[i])) {
            stack[++top] = tolower(s[i]);
        }
    }
    
    for (int i = 0; s[i] != '\0'; i++) {
        if (isalnum(s[i])) {
            if (tolower(s[i]) != stack[top--]) {
                return false;
            }
        }
    }
    
    return top == -1;
}

def isPalindromeWithStack(s: str) -> bool:
    stack = []
    for c in s:
        if c.isalnum():
            stack.append(c.lower())
    
    for c in s:
        if c.isalnum():
            if c.lower() != stack.pop():
                return False
    
    return len(stack) == 0

func isPalindromeWithStack(s string) bool {
    stack := make([]byte, 0)
    for _, c := range s {
        if isAlnum(c) {
            stack = append(stack, toLower(c))
        }
    }
    
    for _, c := range s {
        if isAlnum(c) {
            topChar := stack[len(stack)-1]
            stack = stack[:len(stack)-1]
            if toLower(c) != topChar {
                return false
            }
        }
    }
    
    return len(stack) == 0
}
// isAlnum 和 toLower 函数与前面的Golang版本相同