回文是一个向前和向后读起来都一样的字符串。检查字符串是否为回文可以使用迭代和递归方法来完成。
- 回文是指前后读法相同的单词。例如,考虑单词 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 循环,递归方法使用递归部分的辅助函数。