回文是一个向前和向后读起来都一样的字符串。检查字符串是否为回文可以使用迭代和递归方法来完成。
- 回文是指前后读法相同的单词。例如，考虑单词 RACECAR，如果我们向后读它，它将与向前读相同。
- 为了编写一个检查回文的逻辑，我们可以使用 2 个指针并将它们向内移动。这样做的同时我们可以将角色等同起来。我们可以这样做，直到两个指针位于同一索引上或彼此交叉。
- 在向内移动索引时，如果我们看到字符不匹配的情况，那么我们可以立即返回 false，否则一旦完成迭代我们就返回 true。
伪代码：
define two pointers, left and right.
- - 左 = 字符串的起点，右 = 字符串的终点
int i=0;
int j=s.length()-1;
move the window
- 如果左侧字符和右侧字符相等，则继续缩小窗口
- 如果左侧字符和右侧字符不相等，立即返回
while(i<j){
if(s.charAt(i)!=s.charAt(j)){
return false;
}
i++;
j--;
}
return true;
|
以下是这两种方法的 Python 示例：
迭代方法：
def is_palindrome_iterative(s):
# 移除空格并转换为小写，以便进行不区分大小写的比较
s = ''.join(s.split()).lower()
# 初始化字符串开头和结尾的指针
start, end = 0, len(s) - 1
# 初始化字符串开头和结尾的指针
while start < end:
# If characters at the pointers are not equal, it's not a palindrome
if s[start] != s[end]:
return False
start += 1
end -= 1
如果循环完成，则字符串为回文字符串
return True
# Example usage:
string_to_check = "A man a plan a canal Panama"
result = is_palindrome_iterative(string_to_check)
print(f'"{string_to_check}" is a palindrome: {result}')
Java迭代：
public boolean validate(String s){
int i=0;
int j=s.length()-1;
while(i<j){
if(s.charAt(i)!=s.charAt(j)){
return false;
}
i++;
j--;
}
return true;
|
递归方法：
def is_palindrome_recursive(s):
# 递归检查字符串是否为回文的辅助函数
def is_palindrome_helper(start, end):
# 基本情况：如果指针在中间相遇，则是回文
if start >= end:
return True
# 检查指针上的字符是否相等
if s[start] != s[end]:
return False
# 将指针移向中心并递归
return is_palindrome_helper(start + 1, end - 1)
# 删除空格并转换为小写进行不区分大小写的比较
s = ''.join(s.split()).lower()
# 从字符串的全长开始递归
return is_palindrome_helper(0, len(s) - 1)
# Example usage:
string_to_check = "A man a plan a canal Panama"
result = is_palindrome_recursive(string_to_check)
print(f'"{string_to_check}" is a palindrome: {result}')
Java递归：
public boolean validateRec(String s, int left, int right){
if(left>=right){
return true;
}
if(s.charAt(left)!=s.charAt(right)){
return false;
}
return validateRec(s, left+1, right-1);
}
|
这两种方法的工作原理都是比较字符串开头和结尾的字符，检查它们是否相同。迭代方法使用 while 循环，递归方法使用递归部分的辅助函数。