- 作者简介：阿里非典型程序员一枚 ，记录在大厂的打怪升级之路。 一起学习Java、大数据、数据结构算法（公众号同名）
- ❤️觉得文章还不错的话欢迎大家点赞👍➕收藏⭐️➕评论，💬支持博主，记得点个大大的
关注，持续更新🤞
————————————————-
首先，请注意您提供的题目链接是 LeetCode 14，但题目描述和代码实现应该对应于 LeetCode 125（验证回文串）。以下是按照您要求的格式编写的技术博客。
题目描述
给定一个字符串，判断它是否是回文串，只考虑字母和数字字符，可以忽略字母的大小写。
思路及实现
方式一：双指针
思路
从字符串的两端向中间遍历，跳过非字母和数字的字符，比较对应的字符是否相等。
代码实现
Java版本
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; }
说明：使用双指针从字符串两端向中间遍历，跳过非字母和数字的字符，比较对应字符（转换为小写后）是否相等。
C语言版本
#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; }
说明：C语言版本与Java版本类似，但使用了C标准库中的函数来处理字符。
Python3版本
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
说明：Python版本与Java版本思路相同，但语法不同。
Golang版本
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 }
说明：Golang版本也实现了双指针的逻辑，并额外定义了辅助
复杂度分析
- 时间复杂度：O(n)，其中 n 是字符串的长度。在最坏情况下，我们需要遍历整个字符串一次。
- 空间复杂度：O(1)，我们使用了常数级别的额外空间来存储指针和变量。
方式二：辅助栈
思路
我们可以使用一个栈来存储字符串的前半部分（忽略非字母和数字字符），然后逐个与字符串的后半部分（同样忽略非字母和数字字符）进行比较。
代码实现
Java版本
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(); }
说明：首先将字符串中的字母和数字字符（转换为小写）压入栈中，然后再次遍历字符串并与栈顶字符进行比较。
C语言版本
由于C语言没有内建的栈，我们通常会使用数组来模拟栈的行为。
#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; }
说明：使用数组模拟栈的行为，首先将字母和数字字符压入栈中，然后再次遍历字符串并与栈顶字符进行比较。
Python3版本
Python中的列表可以作为栈使用。
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
说明：Python版本使用列表作为栈，首先将字母和数字字符压入栈中，然后再次遍历字符串并与栈顶字符进行比较。
Golang版本
在Golang中，我们也可以使用切片（slice）来模拟栈。
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版本相同
说明：Golang版本使用切片作为栈，首先将字母和数字字符压入栈中，然后再次遍历字符串并与栈顶字符进行比较。
复杂度分析
- 时间复杂度：O(n)，其中 n 是字符串的长度。我们需要遍历整个字符串两次，一次用于压栈，一次用于比较。
- 空间复杂度：O(n)，在最坏情况下，我们需要将字符串中的所有字母和数字字符都压入栈中，因此栈的大小与字符串的长度成正比。但在实际情况中，由于我们只存储了字母和数字字符，所以空间复杂度可能会
总结
| 方式 | 优点 | 缺点 | 时间复杂度 | 空间复杂度 |
| 双指针法 | 代码简洁，时间效率高 | 依赖于字符串的结构，对于非回文字符串需要遍历整个字符串 | O(n) | O(1) |
| 辅助栈法 | 逻辑清晰，易于理解 | 需要额外的空间来存储栈，可能不是最优解 | O(n) | O(n) |
注意：在辅助栈法中，虽然空间复杂度是O(n)，但在实际情况下，由于我们只存储了字母和数字字符，所以空间复杂度可能会低于O(n)。
相似题目
注意：这些题目可能不仅涉及回文字符串的验证，还可能包括回文子串、回文链表等不同的变种，但都与回文的概念相关。
欢迎一键三连(关注+点赞+收藏)，技术的路上一起加油！！！代码改变世界
- 关于我：阿里非典型程序员一枚 ，记录在大厂的打怪升级之路。 一起学习Java、大数据、数据结构算法（公众号同名），回复暗号，更能获取学习秘籍和书籍等
