语言不可知-如何检查给定的字符串是否是回文?

定义:

回文是一个单词,词组,数字或其他单位序列,其特征是可以在任一方向上读取相同内容

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

这是前一段时间的FAIQ(常见访谈问题)之一,但大部分使用C。

寻找任何可能的语言解决方案。

Prakash asked 2019-11-07T16:16:09Z
30个解决方案
46 votes

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

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

ConroyP answered 2019-11-07T16:16:29Z
34 votes

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
Paulius answered 2019-11-07T16:16:55Z
29 votes

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

rev = StringReverse(originalString)
return ( rev == originalString );
Tnilsson answered 2019-11-07T16:17:21Z
24 votes

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 answered 2019-11-07T16:17:54Z
15 votes

C#:LINQ

var str = "a b a";
var test = Enumerable.SequenceEqual(str.ToCharArray(), 
           str.ToCharArray().Reverse());
aku answered 2019-11-07T16:18:21Z
14 votes

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

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

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

Brian Warshaw answered 2019-11-07T16:18:52Z
11 votes

未优化的Python:

>>> def is_palindrome(s):
...     return s == s[::-1]
Blair Conrad answered 2019-11-07T16:19:23Z
11 votes

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 answered 2019-11-07T16:19:49Z
10 votes

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

将一半的字符推入堆栈(长度/ 2)。
弹出并比较每个字符,直到第一个不匹配为止。
如果堆栈具有零元素:回文。
*对于长度为奇数的字符串,请丢弃中间的字符。

xanadont answered 2019-11-07T16:20:54Z
10 votes

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

对于“赛车”,“赛车”,“赛车”,“赛车”和“赛车”来说,将返回true。 修改为同时包含符号或空格会很容易,但是我认为仅计算字母(忽略大小写)会更有用。 这适用于我在此处的答案中找到的所有回文,并且我无法将其欺骗为假阴性/阳性。

另外,如果您不喜欢“ C”程序中的bool,则显然可以返回int,对于true和false分别返回1和0。

Hostile answered 2019-11-07T16:21:37Z
8 votes

这是一种python方式。 注意:这并不是真正的“ 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
Baltimark answered 2019-11-07T16:22:07Z
6 votes
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;
gabr answered 2019-11-07T16:22:29Z
6 votes

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

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

“一个人,一个计划,一条运河,巴拿马。”

“丰田就是丰田。”

“一种”

以及一些非回文症。

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;
}
Wedge answered 2019-11-07T16:24:13Z
6 votes

编辑:从评论:

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

C ++方式。

我朴素的实现使用优雅的迭代器。 实际上,您可能会检查并在您的前向迭代器超过字符串的一半时停止。

#include <string>
#include <iostream>

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." <<endl;
    cout << "String b: \"" << b << "\" is " << ((palindrome(b))? "" : "not ") << "a palindrome." <<endl;

}
Flame answered 2019-11-07T16:24:51Z
4 votes
boolean isPalindrome(String str1) {
  //first strip out punctuation and spaces
  String stripped = str1.replaceAll("[^a-zA-Z0-9]", "");
  return stripped.equalsIgnoreCase((new StringBuilder(stripped)).reverse().toString());
}

Java版本

Ryan Ahearn answered 2019-11-07T16:25:16Z
3 votes

这是我的解决方案,无需使用strrev。 用C#编写,但可以在具有字符串长度功能的任何语言中使用。

private static bool Pal(string s) {
    for (int i = 0; i < s.Length; i++) {
        if (s[i] != s[s.Length - 1 - i]) {
            return false;
        }
    }
    return true;
}
swilliams answered 2019-11-07T16:25:40Z
3 votes

这是我在C#中的解决方案

static bool isPalindrome(string s)
{
    string allowedChars = "abcdefghijklmnopqrstuvwxyz"+
        "1234567890ABCDEFGHIJKLMNOPQRSTUVWXYZ";
    string compareString = String.Empty;
    string rev = string.Empty;

    for (int i = 0; i <= s.Length - 1; i++)
    {
        char c = s[i];

        if (allowedChars.IndexOf(c) > -1)
        {
            compareString += c;
        }
    }


    for (int i = compareString.Length - 1; i >= 0; i--)
    {
        char c = compareString[i];
        rev += c;
    }

    return rev.Equals(compareString, 
        StringComparison.CurrentCultureIgnoreCase);
}
Jared answered 2019-11-07T16:26:07Z
3 votes

这是处理不同情况,标点符号和空格的Python版本。

import string

def is_palindrome(palindrome):
    letters = palindrome.translate(string.maketrans("",""),
                  string.whitespace + string.punctuation).lower()
    return letters == letters[::-1]

编辑:无耻地偷走了布莱尔·康拉德(Blair Conrad)的整洁答案,从我以前的版本中删除了稍微笨拙的列表处理。

Dave Webb answered 2019-11-07T16:26:40Z
3 votes

C ++

std::string a = "god";
std::string b = "lol";

std::cout << (std::string(a.rbegin(), a.rend()) == a) << " " 
          << (std::string(b.rbegin(), b.rend()) == b);

重击

function ispalin { [ "$( echo -n $1 | tac -rs . )" = "$1" ]; }
echo "$(ispalin god && echo yes || echo no), $(ispalin lol && echo yes || echo no)"

古努·阿克(Gnu Awk)

/* obvious solution */
function ispalin(cand, i) { 
    for(i=0; i<length(cand)/2; i++) 
        if(substr(cand, length(cand)-i, 1) != substr(cand, i+1, 1)) 
            return 0; 
    return 1; 
}

/* not so obvious solution. cough cough */
{ 
    orig = $0;
    while($0) { 
        stuff = stuff gensub(/^.*(.)$/, "\\1", 1); 
        $0 = gensub(/^(.*).$/, "\\1", 1); 
    }
    print (stuff == orig); 
}

哈斯克尔

在Haskell中一些脑筋急转弯的方式

ispalin :: [Char] -> Bool
ispalin a = a == (let xi (y:my) = (xi my) ++ [y]; xi [] = [] in \x -> xi x) a

普通英语

"Just reverse the string and if it is the same as before, it's a palindrome"

Johannes Schaub - litb answered 2019-11-07T16:27:37Z
3 votes

红宝石:

class String
    def is_palindrome?
        letters_only = gsub(/\W/,'').downcase
        letters_only == letters_only.reverse
    end
end

puts 'abc'.is_palindrome? # => false
puts 'aba'.is_palindrome? # => true
puts "Madam, I'm Adam.".is_palindrome? # => true
Matchu answered 2019-11-07T16:27:56Z
3 votes

混淆的C版本:

int IsPalindrome (char *s)
{
  char*a,*b,c=0;
  for(a=b=s;a<=b;c=(c?c==1?c=(*a&~32)-65>25u?*++a,1:2:c==2?(*--b&~32)-65<26u?3:2:c==3?(*b-65&~32)-(*a-65&~32)?*(b=s=0,a),4:*++a,1:0:*++b?0:1));
  return s!=0;
}
Skizz answered 2019-11-07T16:28:24Z
2 votes

此Java代码应在布尔方法内工作:

注意:您只需要检查字符的前半部分和后半部分,否则您将需要进行的检查数量重叠和加倍。

private static boolean doPal(String test) {
    for(int i = 0; i < test.length() / 2; i++) {
        if(test.charAt(i) != test.charAt(test.length() - 1 - i)) {
            return false;
        }
    }
    return true;
}
Kamikaze Mercenary answered 2019-11-07T16:29:03Z
2 votes

另一个C ++。 针对速度和大小进行了优化。

bool is_palindrome(const std::string& candidate) {
    for(std::string::const_iterator left = candidate.begin(), right = candidate.end(); left < --right ; ++left)
        if (*left != *right)
            return false;
    return true;
}

Leon Timmermans answered 2019-11-07T16:29:35Z
2 votes

Lisp:

(defun palindrome(x) (string= x (reverse x)))
Alexander Stolz answered 2019-11-07T16:30:02Z
2 votes

从最笨拙到正确的Smalltalk中的三个版本。


在Smalltalk中,Collection是比较运算符:

isPalindrome: aString
    "Dumbest."
    ^ aString reverse = aString

消息Collection返回字符串为小写字母:

isPalindrome: aString
    "Case insensitive"
    |lowercase|
    lowercase := aString translateToLowercase.
    ^ lowercase reverse = lowercase

在Smalltalk中,字符串是Collection框架的一部分,您可以使用消息#select:thenCollect:,所以这是最后一个版本:

isPalindrome: aString
    "Case insensitive and keeping only alphabetic chars
    (blanks & punctuation insensitive)."
    |lowercaseLetters|
    lowercaseLetters := aString
        select: [:char | char isAlphabetic]
        thenCollect: [:char | char asLowercase]. 
    ^ lowercaseLetters reverse = lowercaseLetters
Sébastien RoccaSerra answered 2019-11-07T16:30:51Z
2 votes

请注意,在上述C ++解决方案中,存在一些问题。

一种解决方案之所以效率低下,是因为它逐个传递了std :: string,并且它遍历了所有字符,而不是只比较一半字符。 然后,即使发现字符串不是回文,它也会继续循环,在报告“ false”之前等待其结束。

另一个更好,它的函数很小,问题是除了std :: string之外,它无法测试其他任何东西。 在C ++中,很容易将算法扩展到一堆类似的对象。 通过将其std :: string模板化为“ T”,它将对std :: string,std :: wstring,std :: vector和std :: deque都起作用。 但是由于没有使用运算符<进行重大修改,因此std :: list不在其范围内。

我自己的解决方案试图证明C ++解决方案不会仅仅停留在确切的当前类型上,而是将努力工作任何行为都相同的方式,无论类型如何。 例如,我可以在std :: string,int的向量或“ Anything”的列表上应用回文检验,只要Anything可通过其操作符=(构建类型和类)进行比较即可。

请注意,甚至可以使用可用于比较数据的可选类型扩展模板。 例如,如果您想以不区分大小写的方式进行比较,或者甚至比较相似的字符(例如è,é,ë,ê和e)。

就像列奥尼达斯国王会说:“模板?这是C ++ !!!”

因此,在C ++中,至少有3种主要方法可以做到这一点,每种方法都可以导致另一种方法:

解决方案A:采用类似C的方式

问题在于,直到C ++ 0X,我们才能将char的std :: string数组视为连续的,因此我们必须“作弊”并检索c_str()属性。 由于我们以只读方式使用它,因此应该可以...


bool isPalindromeA(const std::string & p_strText)
{
   if(p_strText.length() < 2) return true ;
   const char * pStart = p_strText.c_str() ;             
   const char * pEnd = pStart + p_strText.length() - 1 ; 

   for(; pStart < pEnd; ++pStart, --pEnd)
   {
      if(*pStart != *pEnd)
      {
         return false ;
      }
   }

   return true ;
}

解决方案B:更多的“ C ++”版本

现在,我们将尝试应用相同的解决方案,但将其应用于任何通过操作符[]随机访问其项目的C ++容器。 例如,任何std :: basic_string,std :: vector,std :: deque等。Operator []是对这些容器的恒定访问,因此我们不会损失不必要的速度。


template <typename T>
bool isPalindromeB(const T & p_aText)
{
   if(p_aText.empty()) return true ;
   typename T::size_type iStart = 0 ;
   typename T::size_type iEnd = p_aText.size() - 1 ;

   for(; iStart < iEnd; ++iStart, --iEnd)
   {
      if(p_aText[iStart] != p_aText[iEnd])
      {
         return false ;
      }
   }

   return true ;
}

解决方案C:模板powah!

它几乎可以与任何带有双向迭代器的无序STL类容器一起使用例如,任何std :: basic_string,std :: vector,std :: deque,std :: list等。因此,可以在以下情况下将此功能应用于所有类似STL的容器:1-T是带有双向迭代器的容器2-T的迭代器指向可比较的类型(通过operator =)


template <typename T>
bool isPalindromeC(const T & p_aText)
{
   if(p_aText.empty()) return true ;
   typename T::const_iterator pStart = p_aText.begin() ;
   typename T::const_iterator pEnd = p_aText.end() ;
   --pEnd ;

   while(true)
   {
      if(*pStart != *pEnd)
      {
         return false ;
      }

      if((pStart == pEnd) || (++pStart == pEnd))
      {
         return true ;
      }

      --pEnd ;
   }
}

paercebal answered 2019-11-07T16:32:57Z
2 votes

一个简单的Java解决方案:

public boolean isPalindrome(String testString) {
    StringBuffer sb = new StringBuffer(testString);
    String reverseString = sb.reverse().toString();

    if(testString.equalsIgnoreCase(reverseString)) {
        return true;
    else {
        return false;
    }
}
Ascalonian answered 2019-11-07T16:33:23Z
1 votes

有很多方法可以做到。 我想关键是要以最有效的方式做到这一点(不循环字符串)。 我会将其作为可以轻松逆转的char数组(使用C#)进行。

string mystring = "abracadabra";

char[] str = mystring.ToCharArray();
Array.Reverse(str);
string revstring = new string(str);

if (mystring.equals(revstring))
{
    Console.WriteLine("String is a Palindrome");
}
Ryan Farley answered 2019-11-07T16:33:50Z
1 votes

在Ruby中,转换为小写并剥离所有非字母的内容:

def isPalindrome( string )
    ( test = string.downcase.gsub( /[^a-z]/, '' ) ) == test.reverse
end

但这感觉就像在作弊,对吗? 没有指针或任何东西! 所以这也是C版本,但没有小写字母和字符剥离优势:

#include <stdio.h>
int isPalindrome( char * string )
{
    char * i = string;
    char * p = string;
    while ( *++i ); while ( i > p && *p++ == *--i );
    return i <= p && *i++ == *--p;
}
int main( int argc, char **argv )
{
    if ( argc != 2 )
    {
        fprintf( stderr, "Usage: %s <word>\n", argv[0] );
        return -1;
    }
    fprintf( stdout, "%s\n", isPalindrome( argv[1] ) ? "yes" : "no" );
    return 0;
}

好吧,那很有趣-我能得到这份工作吗?

kranzky answered 2019-11-07T16:34:30Z
1 votes

使用Java,使用Apache Commons String Utils:

public boolean isPalindrome(String phrase) {
  phrase = phrase.toLowerCase().replaceAll("[^a-z]", "");
  return StringUtils.reverse(phrase).equals(phrase);
}
SCdF answered 2019-11-07T16:34:57Z
translate from https://stackoverflow.com:/questions/52002/how-to-check-if-the-given-string-is-palindrome