如何检查给定的字符串是否为回文？

Question

定义：

回文是指一个单词、短语、数字或其他序列，在正反方向上读取时具有相同的属性。

如何检查给定的字符串是否是回文？

这曾经是一道常见面试问题，但大多数情况下使用的是 C 语言。

寻找任何一种语言的解决方案。

- Prakash

---

一个男人，一个计划，一个运河，巴拿马。 - Jonathan

去挂一条萨拉米。我是占着意大利卷的贪吃鬼。 - xanadont

你在意标点符号吗？大小写呢？对于区域敏感的大小写折叠有什么看法？ - erickson

好的，我没有考虑到可以忽略的标点问题！ - prakash

我很失望，据我所知，没有人用堆栈实现它。 - Nick Hodges

@NickHodges，我同意。在迭代字符串时，推入每个字符并弹出并比较。 - BajaBob

Answer 1

PHP示例:

$string = "A man, a plan, a canal, Panama";

function is_palindrome($string)
{
    $a = strtolower(preg_replace("/[^A-Za-z0-9]/","",$string));
    return $a==strrev($a);
}

移除任何非字母数字字符（空格、逗号、感叹号等），以允许像上面那样的完整句子，以及简单的单词。

- PConroy

---

除了英语以外的数字和语言不适用。 - jfs

为什么不先使用strtolower()函数来缩短正则表达式呢？ - Chris Lutz

Answer 2

适用于Windows XP（可能也适用于2000）或更高版本的批处理脚本：

@echo off

call :is_palindrome %1
if %ERRORLEVEL% == 0 (
    echo %1 is a palindrome
) else (
    echo %1 is NOT a palindrome
)
exit /B 0

:is_palindrome
    set word=%~1
    set reverse=
    call :reverse_chars "%word%"
    set return=1
    if "$%word%" == "$%reverse%" (
        set return=0
    )
exit /B %return%

:reverse_chars
    set chars=%~1
    set reverse=%chars:~0,1%%reverse%
    set chars=%chars:~1%
    if "$%chars%" == "$" (
        exit /B 0
    ) else (
        call :reverse_chars "%chars%"
    )
exit /B 0

- pam

Answer 3

语言无关的元代码如下...

rev = StringReverse(originalString)
return ( rev == originalString );

- Tnilsson

---

像这样的解决方案很不错，因为它们容易跟随。有循环、堆栈等的解决方案也很好，但比起这个解决方案更难检查。这只需要一两行代码就可以将其修剪为固定字母表（只包含 [a-zA-Z] 字符）即可。 - Michael Haren

你需要先从字符串中删除空格，否则像“a man a plan a canal panama”这样的回文将无法正确检查。 - Justin Bennett

它不检查回文是否是单词，比如 "no means no"。 - Shabbyrobe

考虑到这个答案是错误的，我很惊讶它会被投票得这么高。正如一些人所指出的，它不适用于所有回文，特别是带有标点符号等情况。众人的智慧啊... - SCdF

然而，根据回文的严格定义，这确实可行。该定义没有说明“反向阅读相同”是什么意思，因此，这种以字符为单位的严格比较方法是最简单的算法。 - cdeszaq

Answer 4

C# 原地算法，任何预处理，如大小写不敏感性或去除空格和标点符号应在将其传递给此函数之前完成。

boolean IsPalindrome(string s) {
    for (int i = 0; i < s.Length / 2; i++)
    {
        if (s[i] != s[s.Length - 1 - i]) return false;
    }
    return true;
}

---

编辑： 在循环条件中删除不必要的"+1"，并将节省下来的比较用于删除冗余的长度比较。感谢评论者！

- David Schmitt

---

我觉得你那里有一个良性的栅栏误差。 - Imbue

抱歉，我说的是 s.Length / 2 + 1。这个加一似乎只会让你检查奇数长度单词的中间字母或偶数长度单词的中间两个字母两次。 - Imbue

我已经同意了Imbue。考虑s = 'aba'：s.Length / 2 == 1 -> i<=1 -> s[1] = s[3 - 1 - 1]（不必要的中间字母自我比较）或s ='ab'：s.Length / 2 == 1 -> i <= 1 -> s[1] = s[2 - 1 - 1]（字母重复检查不必要）。 - jfs

此外，空字符串是否为回文字符串并不清楚。 - jfs

if (s.Length < 2) 是多余的。如果 s.Length < 2，则 s.Length / 2 == 0，因此 i < 0 == false -> 返回 true。 - jfs

Answer 5

C#: LINQ

var str = "a b a";
var test = Enumerable.SequenceEqual(str.ToCharArray(), 
           str.ToCharArray().Reverse());

- aku

---

不错！但在我看来有点过度设计了。 - Abhijeet Patel

Answer 6

对 Hal 的 Ruby 版本 进行更加符合 Ruby 风格的重写：

class String
  def palindrome?
    (test = gsub(/[^A-Za-z]/, '').downcase) == test.reverse
  end
end

现在您可以在任何字符串上调用palindrome?。

- Brian Warshaw

Answer 7

未优化的Python：

>>> def is_palindrome(s):
...     return s == s[::-1]

- Blair Conrad

---

我尝试了，我经常失败，但这次似乎不会。谢谢。 - Blair Conrad

我本来想建议你编辑你的答案，从我下面的答案中添加空格和标点符号处理，但那样就不会那么漂亮了。 :-) - David Webb

像这样的一行函数可以用lambda实现： is_palindrome=lambda s:s == s[::-1] - rjmunro

为什么要创建一个函数呢，当你可以直接使用“is_palindrome = s == s[::-1]”呢？ ;) - Anders Sandvig

Anders Sandvig：为了可读性？如果我们像Dave Webb一样忽略空格和标点符号，可能会更容易维护？ - Blair Conrad

它对不支持扩展切片的序列无效。http://www.python.org/doc/2.5.2/ref/slicings.html。但是 def ispal(iterable): s = list(iterable); return s == s[::-1] 是有效的。 - jfs

Answer 8

Java解决方案：

public class QuickTest {

public static void main(String[] args) {
    check("AmanaplanacanalPanama".toLowerCase());
    check("Hello World".toLowerCase());
}

public static void check(String aString) {
    System.out.print(aString + ": ");
    char[] chars = aString.toCharArray();
    for (int i = 0, j = (chars.length - 1); i < (chars.length / 2); i++, j--) {
        if (chars[i] != chars[j]) {
            System.out.println("Not a palindrome!");
            return;
        }
    }
    System.out.println("Found a palindrome!");
}

}

- Jonathan

---

这个是否经过优化，我猜测运行时间为0(N)。 - Rahul Kumar

Answer 9

大家好，这里是C语言。 （不确定您是否希望在此处提供C语言示例）

bool IsPalindrome(char *s)
{
    int  i,d;
    int  length = strlen(s);
    char cf, cb;

    for(i=0, d=length-1 ; i < length && d >= 0 ; i++ , d--)
    {
        while(cf= toupper(s[i]), (cf < 'A' || cf >'Z') && i < length-1)i++;
        while(cb= toupper(s[d]), (cb < 'A' || cb >'Z') && d > 0       )d--;
        if(cf != cb && cf >= 'A' && cf <= 'Z' && cb >= 'A' && cb <='Z')
            return false;
    }
    return true;
}

对于"racecar", "Racecar", "race car", "racecar ", 和 "RaCe cAr"，该程序会返回true。如果需要考虑符号或空格，也很容易进行修改，不过我认为只统计字母(忽略大小写)更加实用。这个程序适用于我在这里找到的所有回文，我也无法通过任何手段让它产生假阴性或假阳性。

此外，如果你不喜欢在"C"程序中使用bool，显然可以改为返回int，其中return 1表示true，return 0表示false。

- Hostile

---

当然，总是喜欢C语言的解决方案 :) - prakash

我认为你可以优化退出条件为： for( ...; d>=i; ... ) 这将减少执行时间一半。 - Uri London

Answer 10

使用良好的数据结构通常有助于给教授留下深刻印象：

将一半字符推入堆栈（长度/ 2）。 弹出并比较每个字符，直到第一个不匹配为止。 如果堆栈没有元素：回文。 *在长度为奇数的字符串的情况下，抛掉中间字符。

- xanadont

---

使用O(n)的内存，而可以使用原地算法的情况下，可能无法给教授留下深刻印象。 - David Schmitt

一个下推自动机如何知道中间在哪里？;P - sleeplessnerd

回答sleeplessnerd的问题，你可以使用freelist。本质上，它是第二个堆栈，随着第一个堆栈的增长而缩小。不过，在逻辑测试中这可能会过度杀伤，例如if stack1.length() == 2.length()。 - Stephen J