回文是指正读、反读均相同的字符序列,如“abba” 和 “abdba” 均是回文,但“good”不是回文。试设计算法判定给定的字符序列是否为回文。(提示:将一半字符人栈。)以Java或c语言为例子
时间: 2024-10-23 18:15:38 浏览: 28
回文数是指正读和反读都相同的数.docx
在Java中,你可以采用双指针法和栈的数据结构来设计一个判断字符串是否为回文的算法。这里是一个简单的Java示例:
```java
public class Solution {
public boolean isPalindrome(String s) {
// 删除非字母数字字符并转换为小写
String cleanStr = s.replaceAll("[^a-zA-Z0-9]", "").toLowerCase();
// 初始化两个指针,一个从头开始,一个从尾部结束
int start = 0;
int end = cleanStr.length() - 1;
// 使用栈存储左半部分字符
Stack<Character> stack = new Stack<>();
while (start < end) {
// 入栈左半部分字符
stack.push(cleanStr.charAt(start));
start++;
// 出栈并与右半部分字符比较
if (!stack.isEmpty() && stack.peek() != cleanStr.charAt(end)) {
return false; // 相符失败,不是回文
}
end--;
}
// 如果所有字符都检查过了,且栈为空或者只剩下一个字符,那么它是回文
return stack.isEmpty() || (stack.size() == 1 && start == end);
}
public static void main(String[] args) {
Solution solution = new Solution();
System.out.println(solution.isPalindrome("A man, a plan, a canal: Panama")); // 输出 true
System.out.println(solution.isPalindrome("race a car")); // 输出 false
}
}
```
这个算法首先清理输入字符串,然后通过双指针同时推进,一个指向字符串开头,一个指向结尾。将每个字符依次入栈,然后出栈与对应的字符进行比较。如果任何时候发现不匹配,则返回false;当所有的字符都成功比较完毕,说明原始字符串是回文。
阅读全文