如何检查给定的string是回文？
定义：
回文是一个单词，短语，数字或其他单元序列，具有在任一方向读取相同的属性
如何检查给定的string是否是回文？
这是FAIQ [常问问题采访问题]之一，但主要使用C.
以任何和所有语言寻找解决scheme。
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); } 删除任何非字母数字字符（空格，逗号，感叹号等），以允许上面的完整句子，以及简单的单词。
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
语言不可知的元代码，然后…
rev = StringReverse(originalString) return ( rev == originalString );
C＃就地algorithm。 任何预处理，如不区分大小写，或者空格和标点符号的剥离都应该在传递给该函数之前完成。
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 ”，并花费保存的比较去除冗余的长度比较。 感谢评论者！
C＃：LINQ
var str = "aba"; var test = Enumerable.SequenceEqual(str.ToCharArray(), str.ToCharArray().Reverse());
Hal的Ruby版本更为ruby式的重写：
class String def palindrome? (test = gsub(/[^A-Za-z]/, '').downcase) == test.reverse end end
现在你可以打回电了palindrome? 在任何string上。
未优化的Python：
>>> def is_palindrome(s): ... return s == s[::-1]
Java解决scheme：
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!"); }
}
使用好的数据结构通常有助于给教授留下深刻的印象：
将一半的字符推入堆栈（长度/ 2）。
popup并比较每个字符，直到第一个不匹配。
如果堆栈有零元素：回文。
*在一个奇数长度的string的情况下，抛出中间字符。
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”，这将是真实的。 修改包括符号或空格也很容易，但是我认为只计算字母（而忽略大小写）会更有用。 这适用于我在这里find答案的所有回文，我一直无法欺骗它的假阴性/积极。
另外，如果你不喜欢“C”程序中的bool，它显然可以返回int，返回1，并分别返回true和false。
这是一个Python的方式。 注意：这不是真正的“pythonic”，但它演示了algorithm。
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
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;
我在这里看到很多不正确的答案。 任何正确的解决scheme都需要忽略空格和标点符号（实际上是任何非字母字符），并且需要不区分大小写。
一些很好的示例testing用例是：
“一个男人，一个计划，一条运河，巴拿马。”
“丰田是丰田。”
“一个”
“”
以及一些非回文。
在C＃中的例子解决scheme（注意：在这个devise中，空string和空string被认为是回文），如果不需要这个，很容易改变）：
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; }
编辑：从评论：
bool palindrome(std::string const& s) { return std::equal(s.begin(), s.end(), s.rbegin()); }
c ++的方式。
我天真的实现使用优雅的迭代器。 事实上，你可能会检查并停止一旦你的迭代器已经超过了你的string的中途标记。
#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; }
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版本
这是我的解决scheme，不使用strrev。 用C＃编写，但它将以任何具有string长度函数的语言工作。
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; }
这是我的解决scheme在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); }
Smalltalk中的三个版本，从最糟糕到正确。
在Smalltalk中， =是比较运算符：
isPalindrome: aString "Dumbest." ^ aString reverse = aString
消息#translateToLowercase以小写#translateToLowercase返回string：
isPalindrome: aString "Case insensitive" |lowercase| lowercase := aString translateToLowercase. ^ lowercase reverse = lowercase
在Smalltalk中，string是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
这里是一个Python版本，处理不同的情况下，标点符号和空白。
import string def is_palindrome(palindrome): letters = palindrome.translate(string.maketrans("",""), string.whitespace + string.punctuation).lower() return letters == letters[::-1]
编辑：无耻地从布莱尔·康拉德的整洁的答案偷走从我以前的版本中删除略显笨拙的列表处理。
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"
ruby：
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
混淆的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; }
这个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; }
另一个C ++之一。 针对速度和尺寸进行了优化。
bool is_palindrome（const std :: string＆candidate）{
for（std :: string :: const_iterator left = candidate.begin（），right = candidate.end（）; left <--right; ++ left）
如果（*左！= *右）
返回false;
返回true;
}
Lisp的：
(defun palindrome(x) (string= x (reverse x)))
注意在上面的C ++解决scheme中，有一些问题。
一个解决scheme效率低下，因为它通过复制传递了一个std :: string，并且因为它迭代了所有的字符，而不是只比较一半的字符。 然后，即使发现string不是回文，它仍然继续循环，在报告“错误”之前等待其结束。
另一个更好，function非常小，问题是它不能testing除std :: string以外的其他东西。 在C ++中，很容易将一个algorithm扩展到一大堆相似的对象。 通过将其std :: string模板化为“T”，它可以在std :: string，std :: wstring，std :: vector和std :: deque上工作。 但是由于使用运算符<，没有进行大的修改，std :: list超出了它的范围。
我自己的解决scheme试图表明，一个C ++解决scheme不会停止在确切的当前types上工作，但会努力工作的行为方式相同，无论types。 例如，只要通过操作符=（构buildtypes以及类），任何东西都可以相比，我就可以将回文testing应用于std :: string，int向量或“Anything”列表中。
请注意，模板甚至可以使用可用于比较数据的可选types进行扩展。 例如，如果要以不区分大小写的方式进行比较，或者甚至比较相似的字符（如è，é，ë，ê和e）。
就像国王列奥尼达斯会说： “模板？这是C ++ !!!”
所以，在C ++中，至less有三种主要的方法可以做到这一点，
解决schemeA：以类似C的方式
问题是，直到C ++ 0X，我们不能认为string的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 ; }
解决schemeB：更“C ++”的版本
现在，我们将尝试应用相同的解决scheme，但通过运算符[]，可以随机访问其项目的任何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 ; }
解决schemeC：模板powah！
它可以和几乎任何无序的STL类容器一起使用，例如，任何std :: basic_string，std :: vector，std :: deque，std :: list等。所以，这个函数可以应用于所有的STL具有以下条件的容器：1 – T是一个双向迭代器2的容器 – T的迭代器指向一个类似的types（通过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 ; } }
简单的Java解决scheme：
public boolean isPalindrome(String testString) { StringBuffer sb = new StringBuffer(testString); String reverseString = sb.reverse().toString(); if(testString.equalsIgnoreCase(reverseString)) { return true; else { return false; } }
许多方法来做到这一点。 我想关键是要以最有效的方式做到这一点（没有循环string）。 我会做一个字符数组，可以很容易地颠倒（使用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"); }
在Ruby中，转换为小写字母并剥离一切不是字母的：
def isPalindrome( string ) ( test = string.downcase.gsub( /[^az]/, '' ) ) == 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; }
那很好玩 – 我能得到这份工作吗？^）
使用Java，使用Apache Commons String Utils：
public boolean isPalindrome(String phrase) { phrase = phrase.toLowerCase().replaceAll("[^az]", ""); return StringUtils.reverse(phrase).equals(phrase); }
