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

定义:

回文是单词,短语,数字或其他单元序列,具有在任一方向上读取相同的属性

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

这是前一段时间的FAIQ [常见问题访谈问题]之一,但主要是使用C.

寻找任何和所有语言的解决方案.

1> ConroyP..：

---

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);
}

删除任何非字母数字字符(空格,逗号,感叹号等),以允许如上所述的完整句子,以及简单的单词.

---

只是好奇 - 为什么不首先strtolower()所以你有一个较短的正则表达式？

---

它不适用于除英语之外的数字和语言.

2> Paulius..：

---

Windows XP(可能也适用于2000)或更高版本的BATCH脚本:

@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

3> Tnilsson..：

---

然后语言不可知的元代码......

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

---

然而,对于回文的严格定义,这确切地起作用.该定义没有指明"在任何一个方向上读取相同"的含义,因此,字符比较的严格字符,这是最简单的算法.

---

考虑到这是错误的,我很惊讶这个被投了很多.正如人们所指出的那样,它不适用于所有的回文,特别是标点符号等.人群的智慧......

4> David Schmit..：

---

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在循环条件中删除不必要的" ",并在删除冗余长度比较时花费了已保存的比较.感谢评论者!

5> aku..：

---

C#:LINQ

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

6> Brian Warsha..：

---

更多Ruby风格的Hal的Ruby版本重写:

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

现在你可以调用palindrome?任何字符串.

7> Blair Conrad..：

---

未经优化的Python:

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

8> Jonathan..：

---

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!");
}

}

9> xanadont..：

---

使用良好的数据结构通常会给教授留下深刻的印象:

将一半字符推入堆栈(长度/ 2).
弹出并比较每个char直到第一个不匹配.
如果堆栈元素为零:回文结构.
*如果字符串具有奇数长度,则抛出中间字符.

10> Hostile..：

---

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;
}

对于"赛车","赛车","赛车","赛车"和"RaCe cAr",这将成为现实.修改包含符号或空格也很容易,但我认为仅计算字母(并忽略大小写)更有用.这适用于我在答案中找到的所有回文,我一直无法将其欺骗为假阴性/阳性.

另外,如果你不喜欢"C"程序中的bool,它显然可以返回int,返回1并分别返回0表示true和false.

---

我认为你可以优化退出条件:for(...; d> = i; ...)它会将执行时间缩短一半

11> Baltimark..：

---

这是一种蟒蛇的方式.注意:这不是真正的"pythonic",但它演示了算法.

def IsPalindromeString(n):
    myLen = len(n)
    i = 0
    while i <= myLen/2:
        if n[i] != n[myLen-1-i]:
            return False
        i += 1
    return True

---

顺便说一下,建议不要将CamelCase用于函数和局部变量名.请参阅"Python代码样式指南"http://www.python.org/dev/peps/pep-0008/

12> gabr..：

---

Delphi

function IsPalindrome(const s: string): boolean;
var
  i, j: integer;
begin
  Result := false;
  j := Length(s);
  for i := 1 to Length(s) div 2 do begin
    if s[i] <> s[j] then
      Exit;
    Dec(j);
  end;
  Result := true;
end;

13> Flame..：

---

编辑:从评论:

bool palindrome(std::string const& s) 
{ 
  return std::equal(s.begin(), s.end(), s.rbegin()); 
} 

---

c ++的方式.

我使用优雅的迭代器实现天真.实际上,一旦你的前向迭代器已超过你的弦的中间标记,你可能会检查并停止.

#include 
#include 

using namespace std;
bool palindrome(string foo)
{
    string::iterator front;
    string::reverse_iterator back;
    bool is_palindrome = true;
    for(front = foo.begin(), back = foo.rbegin();
        is_palindrome && front!= foo.end() && back != foo.rend();
        ++front, ++back
        )
    {
        if(*front != *back)
            is_palindrome = false;
    }
    return is_palindrome;
}
int main()
{
    string a = "hi there", b = "laval";

    cout << "String a: \"" << a << "\" is " << ((palindrome(a))? "" : "not ") << "a palindrome." <

        

14> Wedge..：
我在这里看到了很多不正确的答案.任何正确的解决方案都需要忽略空格和标点符号(实际上是任何非字母字符),并且需要不区分大小写.

一些很好的示例测试用例是:

"一个男人,一个计划,一条运河,巴拿马."

"丰田是一辆丰田汽车."

"一个"

""

以及一些非回文.

C#中的示例解决方案(注意:在此设计中,空字符串和空字符串被视为回文,如果不希望这样,则很容易更改):

public static bool IsPalindrome(string palindromeCandidate)
{
    if (string.IsNullOrEmpty(palindromeCandidate))
    {
        return true;
    }
    Regex nonAlphaChars = new Regex("[^a-z0-9]");
    string alphaOnlyCandidate = nonAlphaChars.Replace(palindromeCandidate.ToLower(), "");
    if (string.IsNullOrEmpty(alphaOnlyCandidate))
    {
        return true;
    }
    int leftIndex = 0;
    int rightIndex = alphaOnlyCandidate.Length - 1;
    while (rightIndex > leftIndex)
    {
        if (alphaOnlyCandidate[leftIndex] != alphaOnlyCandidate[rightIndex])
        {
            return false;
        }
        leftIndex++;
        rightIndex--;
    }
    return true;
}