回文”是指正读反读均相同的字符序列,如“abba”和“abdba”均是回文,但“good”不是回文。请用程序设计语言编写算法,判定给定的字符序列是否为回文。假设字符序列存储在一个字符数组中。(提示:将一半字符入栈,再逐个弹出并比较。注意:要分别考虑字符串长度为奇数和偶数时的情况)
时间: 2024-09-22 11:10:25 浏览: 47
判断一个字符序列是否为回文可以采用双指针法或者栈的数据结构。这里我会提供一个使用Python语言的例子:
```python
def is_palindrome(s):
# 将字符串转为小写并去除空格
s = "".join(c.lower() for c in s if c.isalnum())
# 特殊处理字符串长度为奇数的情况
length = len(s)
if length % 2 == 1:
mid = length // 2
left, right = 0, mid - 1
else:
mid = length // 2
left, right = 0, mid - 1
# 使用栈辅助检查
stack = []
while left <= right:
stack.append(s[left])
left += 1
if left < mid:
stack.append(s[right])
right -= 1
elif s[left] != s[right]:
return False
# 如果所有元素都已匹配,说明是回文
return True
# 测试示例
print(is_palindrome("A man a plan a canal Panama")) # 输出: True
print(is_palindrome("race a car")) # 输出: False
```
在这个算法中,我们首先处理了字符串大小写和非字母数字字符的问题,然后用两个指针`left`和`right`从两端向中间推进。如果遇到不相等的字符或者到了字符串中心,那么就直接返回False,表示不是回文。只有当所有字符都成功匹配后,才返回True。
阅读全文