设计算法,判断回文问题。采用字符串容器存储,设计算法判断该字符串是否为回文。
时间: 2024-11-15 14:27:07 浏览: 15
算法设计与分析课后习题答案(李春保)
3星 · 编辑精心推荐
判断一个字符串是否为回文,可以通过双指针法来解决。算法步骤如下:
1. 创建两个指针,一个指向字符串的开始(`start`),另一个指向字符串的结束(`end`)。
2. 循环条件通常是 `start < end`。在每次迭代中,比较指针所指向的字符:
- 如果两个字符相等(即 `str[start] == str[end]`),则移动指针,让 `start++` 和 `end--`。
- 如果不相等,则说明字符串不是回文,直接返回 `false`。
3. 当 `start >= end` 时,意味着已经检查了所有对称的字符对,都没有发现不匹配的情况,因此字符串是回文,返回 `true`。
以下是一个简单的 Python 示例:
```python
def is_palindrome(s):
s = ''.join(c for c in s if c.isalnum()) # 移除非字母数字字符并转为小写
start, end = 0, len(s) - 1
while start < end:
if s[start] != s[end]:
return False
start, end = start + 1, end - 1
return True
# 使用示例
input_str = "A man, a plan, a canal: Panama"
print(is_palindrome(input_str)) # 输出:True
```
阅读全文