定义：
回文是一个单词、短语、数字或其他单位序列，具有在任一方向阅读相同的属性
如何检查给定的字符串是否是回文？
这是前一段时间的 FAIQ [常见面试问题] 之一，但主要使用 C。
寻找任何和所有语言的解决方案。
Prakash
问问题
137455 次
69 回答
46
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);
}
删除任何非字母数字字符（空格、逗号、感叹号等）以允许使用上述完整句子以及简单单词。
于 2008-09-09T14:42:18.010 回答
34
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
于 2008-09-09T14:36:32.267 回答
30
语言不可知的元代码然后......
rev = StringReverse(originalString)
return ( rev == originalString );
于 2008-09-09T14:29:58.880 回答
24
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”，并将保存的比较用于删除多余的长度比较。感谢评论者！
于 2008-09-09T14:38:07.270 回答
15
C#: LINQ
var str = "a b a";
var test = Enumerable.SequenceEqual(str.ToCharArray(),
str.ToCharArray().Reverse());
于 2008-09-09T14:37:04.573 回答
14
Hal 的 Ruby 版本的更 Ruby 风格的重写：
class String
def palindrome?
(test = gsub(/[^A-Za-z]/, '').downcase) == test.reverse
end
end
现在您可以调用palindrome?任何字符串。
于 2008-09-09T19:52:33.677 回答
11
未优化的 Python：
>>> def is_palindrome(s):
... return s == s[::-1]
于 2008-09-09T14:34:32.067 回答
11
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!");
}
}
于 2008-09-09T14:41:02.817 回答
10
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，返回 1 和返回 0 分别表示 true 和 false。
于 2008-09-09T22:01:54.647 回答
10
使用良好的数据结构通常有助于给教授留下深刻印象：
将一半的字符压入堆栈（长度/2）。
弹出并比较每个字符，直到第一个不匹配。
如果堆栈有零个元素：回文。
*对于奇数长度的字符串，丢弃中间的字符。
于 2008-09-09T14:38:26.020 回答
8
这是一种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
于 2008-09-09T14:35:10.537 回答
6
我在这里看到很多不正确的答案。任何正确的解决方案都需要忽略空格和标点符号（以及实际上任何非字母字符），并且需要不区分大小写。
一些很好的示例测试用例是：
“一个人，一个计划，一条运河，巴拿马。”
“丰田就是丰田。”
“一个”
“”
以及一些非回文。
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;
}
于 2008-09-09T19:14:26.013 回答
6
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;
于 2008-09-09T14:33:44.973 回答
6
编辑：来自评论：
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;
}
于 2008-09-09T14:42:58.913 回答
4
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());
}
爪哇版
于 2008-09-09T14:29:51.860 回答
3
红宝石：
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
于 2009-06-24T16:44:02.627 回答
3
这是我在 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);
}
于 2008-09-09T14:30:30.533 回答
3
这是我的解决方案，不使用 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;
}
于 2008-09-09T14:39:02.213 回答
3
这是一个处理不同情况、标点符号和空格的 Python 版本。
import string
def is_palindrome(palindrome):
letters = palindrome.translate(string.maketrans("",""),
string.whitespace + string.punctuation).lower()
return letters == letters[::-1]
编辑：无耻地从Blair Conrad 的整洁答案中窃取，以删除我以前版本中略显笨拙的列表处理。
于 2008-09-09T14:49:42.907 回答
3
一个混淆的 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;
}
于 2008-09-16T21:46:55.840 回答
3
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)"
牛羚
/* 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"
于 2008-11-10T12:09:11.577 回答
2
语言：
(defun palindrome(x) (string= x (reverse x)))
于 2008-09-12T15:45:58.657 回答
2
请注意，在上述 C++ 解决方案中，存在一些问题。
一种解决方案效率低下，因为它通过复制传递了 std::string，并且因为它迭代了所有字符，而不是只比较一半字符。然后，即使发现字符串不是回文，它也会继续循环，在报告“假”之前等待其结束。
另一个更好，有一个非常小的函数，它的问题是它不能测试除了 std::string 之外的任何东西。在 C++ 中，很容易将算法扩展到一大堆相似的对象。通过将其 std::string 模板化为“T”，它可以在 std::string、std::wstring、std::vector 和 std::deque 上工作。但是由于使用了操作符 < 而没有进行重大修改，std::list 就超出了它的范围。
我自己的解决方案试图表明 C++ 解决方案不会停止在确切的当前类型上工作，而是会努力工作任何行为方式相同的东西，无论类型如何。例如，我可以在 std::string、int 向量或“Anything”列表上应用我的回文测试，只要任何东西都可以通过其运算符 =（内置类型和类）进行比较。
请注意，模板甚至可以使用可用于比较数据的可选类型进行扩展。例如，如果您想以不区分大小写的方式进行比较，或者甚至比较相似的字符（如 è、é、ë、ê 和 e）。
就像列奥尼达国王会说的那样：“模板？这是 C++ ！！！”
因此，在 C++ 中，至少有 3 种主要的方法可以做到这一点，每一种都导致另一种：
解决方案 A：以类似 c 的方式
问题是在 C++0X 之前，我们不能认为 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 等。运算符 [] 是对这些容器的持续访问，因此我们不会失去过度的速度。
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 的迭代器指向可比较的类型（通过运算符 =）
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 ;
}
}
于 2008-09-16T21:56:53.367 回答
2
此 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;
}
于 2008-09-09T14:39:06.613 回答
2
Smalltalk 中的三个版本，从最愚蠢到正确。
在 Smalltalk 中，=是比较运算符：
isPalindrome: aString
"Dumbest."
^ aString reverse = aString
该消息#translateToLowercase以小写形式返回字符串：
isPalindrome: aString
"Case insensitive"
|lowercase|
lowercase := aString translateToLowercase.
^ lowercase reverse = lowercase
而在 Smalltalk 中，字符串是Collection框架的一部分，你可以使用 message #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
于 2008-09-09T15:19:38.560 回答
2
另一个 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;
}于 2008-09-09T15:27:03.050 回答
2
一个简单的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;
}
}
于 2009-03-18T19:40:55.657 回答
1
Python：
if s == s[::-1]: return True
爪哇：
if (s.Equals(s.Reverse())) { return true; }
PHP：
if (s == strrev(s)) return true;
珀尔：
if (s == reverse(s)) { return true; }
二郎：
string:equal(S, lists:reverse(S)).
于 2008-09-11T10:14:27.340 回答
1
珀尔：
sub is_palindrome {
my $s = lc shift; # normalize case
$s =~ s/\W//g; # strip non-word characters
return $s eq reverse $s;
}
于 2008-09-16T02:29:55.463 回答
1
珀尔：
sub is_palindrome($)
{
$s = lc(shift); # ignore case
$s =~ s/\W+//g; # consider only letters, digits, and '_'
$s eq reverse $s;
}
它忽略大小写并去除非字母数字字符（它是区域设置和 unicode 中性的）。
于 2008-09-09T22:35:29.010 回答
1
使用 Java，使用Apache Commons String Utils：
public boolean isPalindrome(String phrase) {
phrase = phrase.toLowerCase().replaceAll("[^a-z]", "");
return StringUtils.reverse(phrase).equals(phrase);
}
于 2008-09-09T23:34:51.100 回答
1
有很多方法可以做到。我想关键是以最有效的方式来做（不循环字符串）。我会将它作为一个可以轻松反转的 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");
}
于 2008-09-09T14:37:38.207 回答
1
在 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;
}
嗯，这很有趣——我能得到这份工作吗 ;^)
于 2008-09-09T16:47:15.183 回答
1
我必须为编程挑战这样做，这是我的 Haskell 的片段：
isPalindrome :: String -> Bool
isPalindrome n = (n == reverse n)
于 2008-09-10T06:08:15.367 回答
1
Simple JavaScript solution. Run code snippet for demo.
function checkPalindrome(line){
reverse_line=line.split("").reverse().join("");
return line==reverse_line;
}
alert("checkPalindrome(radar): "+checkPalindrome("radar"));于 2015-03-20T19:37:30.430 回答
1
序言
palindrome(B, R) :-
palindrome(B, R, []).
palindrome([], R, R).
palindrome([X|B], [X|R], T) :-
palindrome(B, R, [X|T]).
于 2009-07-12T04:45:12.730 回答
1
C++：
bool is_palindrome(const string &s)
{
return equal( s.begin(), s.begin()+s.length()/2, s.rbegin());
}
于 2008-10-23T06:16:13.133 回答
1
还没有使用 JavaScript 的解决方案？
function palindrome(s) {
var l = 0, r = s.length - 1;
while (l < r) if (s.charAt(left++) !== s.charAt(r--)) return false;
return true
}
于 2011-12-29T19:57:25.613 回答
1
我的2c。避免每次全字符串反转的开销，利用短路在确定字符串的性质后立即返回。是的，你应该首先调整你的字符串，但 IMO 那是另一个函数的工作。
在 C# 中
/// <summary>
/// Tests if a string is a palindrome
/// </summary>
public static bool IsPalindrome(this String str)
{
if (str.Length == 0) return false;
int index = 0;
while (index < str.Length / 2)
if (str[index] != str[str.Length - ++index]) return false;
return true;
}
于 2009-06-24T16:31:53.253 回答
1
二郎棒棒哒
palindrome(L) -> palindrome(L,[]).
palindrome([],_) -> false;
palindrome([_|[]],[]) -> true;
palindrome([_|L],L) -> true;
palindrome(L,L) -> true;
palindrome([H|T], Acc) -> palindrome(T, [H|Acc]).
于 2011-11-18T11:31:03.253 回答
0
boolean IsPalindrome(string s) {
return s = s.Reverse();
}
于 2008-09-15T14:23:24.883 回答
0
Efficient C++ version:
template< typename Iterator >
bool is_palindrome( Iterator first, Iterator last, std::locale const& loc = std::locale("") )
{
if ( first == last )
return true;
for( --last; first < last; ++first, --last )
{
while( ! std::isalnum( *first, loc ) && first < last )
++first;
while( ! std::isalnum( *last, loc ) && first < last )
--last;
if ( std::tolower( *first, loc ) != std::tolower( *last, loc ) )
return false;
}
return true;
}
于 2009-01-10T01:15:14.677 回答
0
Here are two more Perl versions, neither of which uses reverse. Both use the basic algorithm of comparing the first character of the string to the last, then discarding them and repeating the test, but they use different methods of getting at the individual characters (the first peels them off one at a time with a regex, the second splits the string into an array of characters).
#!/usr/bin/perl
my @strings = ("A man, a plan, a canal, Panama.", "A Toyota's a Toyota.",
"A", "", "As well as some non-palindromes.");
for my $string (@strings) {
print is_palindrome($string) ? "'$string' is a palindrome (1)\n"
: "'$string' is not a palindrome (1)\n";
print is_palindrome2($string) ? "'$string' is a palindrome (2)\n"
: "'$string' is not a palindrome (2)\n";
}
sub is_palindrome {
my $str = lc shift;
$str =~ tr/a-z//cd;
while ($str =~ s/^(.)(.*)(.)$/\2/) {
return unless $1 eq $3;
}
return 1;
}
sub is_palindrome2 {
my $str = lc shift;
$str =~ tr/a-z//cd;
my @chars = split '', $str;
while (@chars && shift @chars eq pop @chars) {};
return scalar @chars <= 1;
}
于 2009-01-10T01:47:01.043 回答
0
Easy mode in C#, only using Base Class Libraries
Edit: just saw someone did Array.Reverse also
public bool IsPalindrome(string s)
{
if (String.IsNullOrEmpty(s))
{
return false;
}
else
{
char[] t = s.ToCharArray();
Array.Reverse(t);
string u = new string(t);
if (s.ToLower() == u.ToLower())
{
return true;
}
}
return false;
}
于 2009-01-10T02:08:27.380 回答
0
带有堆栈的 Java。
public class StackPalindrome {
public boolean isPalindrome(String s) throws OverFlowException,EmptyStackException{
boolean isPal=false;
String pal="";
char letter;
if (s==" ")
return true;
else{
s=s.toLowerCase();
for(int i=0;i<s.length();i++){
letter=s.charAt(i);
char[] alphabet={'a','b','c','d','e','f','g','h','i','j','k','l','m','n','o','p','q','r','s','t','u','v','w','x','y','z'};
for(int j=0; j<alphabet.length;j++){
/*removing punctuations*/
if ((String.valueOf(letter)).equals(String.valueOf(alphabet[j]))){
pal +=letter;
}
}
}
int len=pal.length();
char[] palArray=new char[len];
for(int r=0;r<len;r++){
palArray[r]=pal.charAt(r);
}
ArrayStack palStack=new ArrayStack(len);
for(int k=0;k<palArray.length;k++){
palStack.push(palArray[k]);
}
for (int i=0;i<len;i++){
if ((palStack.topAndpop()).equals(palArray[i]))
isPal=true;
else
isPal=false;
}
return isPal;
}
}
public static void main (String args[]) throws EmptyStackException,OverFlowException{
StackPalindrome s=new StackPalindrome();
System.out.println(s.isPalindrome("“Ma,” Jerome raps pot top, “Spare more jam!”"));
}
于 2014-05-13T17:38:55.773 回答
0
另一个来自 Delphi，我认为它比提交的另一个 Delphi 示例更严格。这很容易变成一场高尔夫比赛，但我试图让我的可读性。
Edit0：我对性能特征很好奇，所以我做了一点测试。在我的机器上，我针对一个 60 个字符的字符串运行了这个函数 5000 万次，耗时 5 秒。
function TForm1.IsPalindrome(txt: string): boolean;
var
i, halfway, len : integer;
begin
Result := True;
len := Length(txt);
{
special cases:
an empty string is *never* a palindrome
a 1-character string is *always* a palindrome
}
case len of
0 : Result := False;
1 : Result := True;
else begin
halfway := Round((len/2) - (1/2)); //if odd, round down to get 1/2way pt
//scan half of our string, make sure it is mirrored on the other half
for i := 1 to halfway do begin
if txt[i] <> txt[len-(i-1)] then begin
Result := False;
Break;
end; //if we found a non-mirrored character
end; //for 1st half of string
end; //else not a special case
end; //case
end;
在 C# 中，这也是同样的事情，只是我给它留下了多个退出点，这是我不喜欢的。
private bool IsPalindrome(string txt) {
int len = txt.Length;
/*
Special cases:
An empty string is *never* a palindrome
A 1-character string is *always* a palindrome
*/
switch (len) {
case 0: return false;
case 1: return true;
} //switch
int halfway = (len / 2);
//scan half of our string, make sure it is mirrored on the other half
for (int i = 0; i < halfway; ++i) {
if (txt.Substring(i,1) != txt.Substring(len - i - 1,1)) {
return false;
} //if
} //for
return true;
}
于 2008-09-09T14:44:43.963 回答
0
C#3 - 一旦从头开始计数的字符与结尾处的等价字符不匹配，就会返回 false：
static bool IsPalindrome(this string input)
{
char[] letters = input.ToUpper().ToCharArray();
int i = 0;
while( i < letters.Length / 2 )
if( letters[i] != letters[letters.Length - ++i] )
return false;
return true;
}
于 2008-09-09T14:49:25.403 回答
0
如果我们正在寻找数字和简单的单词，已经给出了许多正确的答案。
然而，如果我们正在寻找我们通常认为的书面回文（例如，“A dog, a panic, in a pagoda!”），正确的答案是从句子的两端开始迭代，跳过单独的非字母数字字符，如果发现任何不匹配则返回 false。
i = 0; j = length-1;
while( true ) {
while( i < j && !is_alphanumeric( str[i] ) ) i++;
while( i < j && !is_alphanumeric( str[j] ) ) j--;
if( i >= j ) return true;
if( tolower(string[i]) != tolower(string[j]) ) return false;
i++; j--;
}
当然，去除无效字符、反转结果字符串并将其与原始字符串进行比较也可以。这取决于您正在使用哪种类型的语言。
于 2008-09-10T00:22:50.673 回答
0
于 2008-09-12T09:47:43.947 回答
0
这是我在执行示例服务器控件时使用的另一个 C#。它可以在 ASP.NET 3.5 Step by Step (MS Press) 一书中找到。这是两种方法，一种是去除非字母数字，另一种是检查回文。
protected string StripNonAlphanumerics(string str)
{
string strStripped = (String)str.Clone();
if (str != null)
{
char[] rgc = strStripped.ToCharArray();
int i = 0;
foreach (char c in rgc)
{
if (char.IsLetterOrDigit(c))
{
i++;
}
else
{
strStripped = strStripped.Remove(i, 1);
}
}
}
return strStripped;
}
protected bool CheckForPalindrome()
{
if (this.Text != null)
{
String strControlText = this.Text;
String strTextToUpper = null;
strTextToUpper = Text.ToUpper();
strControlText =
this.StripNonAlphanumerics(strTextToUpper);
char[] rgcReverse = strControlText.ToCharArray();
Array.Reverse(rgcReverse);
String strReverse = new string(rgcReverse);
if (strControlText == strReverse)
{
return true;
}
else
{
return false;
}
}
else
{
return false;
}
}
于 2009-01-10T02:46:45.493 回答
0
常量正确的 C/C++ 指针解决方案。循环中的最小操作。
int IsPalindrome (const char *str)
{
const unsigned len = strlen(str);
const char *end = &str[len-1];
while (str < end)
if (*str++ != *end--)
return 0;
return 1;
}
于 2009-01-10T03:07:59.427 回答
0
public static boolean isPalindrome(String str) {
return str.equals(new StringBuilder(str).reverse().toString());
}
对于早于 1.5 的 Java 版本，
public static boolean isPalindrome(String str) {
return str.equals(new StringBuffer().append(str).reverse().toString());
}
或者
public static boolean istPalindrom(char[] word){
int i1 = 0;
int i2 = word.length - 1;
while (i2 > i1) {
if (word[i1] != word[i2]) {
return false;
}
++i1;
--i2;
}
return true;
}
于 2015-04-12T08:44:50.537 回答
0
这一切都很好，但是有没有办法在算法上做得更好？我曾经在一次采访中被要求识别线性时间和恒定空间中的回文。
我当时什么都想不出来，现在还是想不出来。
（如果有帮助，我问面试官答案是什么。他说你可以构造一对散列函数，当且仅当该字符串是回文时，它们才能将给定的字符串散列到相同的值。我不知道如何你实际上会做这对功能。）
于 2008-11-10T12:05:24.877 回答
0
去除不属于 AZ 或 az 之间的任何字符的解决方案非常以英语为中心。带有 à 或 é 等变音符号的字母将被删除！
根据维基百科：
变音符号的处理方式各不相同。在捷克语和西班牙语等语言中，带有变音符号或重音符号（波浪号除外）的字母在字母表中没有单独的位置，因此无论重复的字母是否有装饰，都可以保留回文。但是，在瑞典语和其他北欧语言中，带环 (å) 的 A 和 A 是不同的字母，必须完全镜像才能被视为真正的回文。
因此，要涵盖许多其他语言，最好使用排序规则将变音符号转换为等效的非变音符号，或者酌情保留，然后仅在比较之前去除空格和标点符号。
于 2008-11-10T14:35:51.607 回答
0
set l = index of left most character in word
set r = index of right most character in word
loop while(l < r)
begin
if letter at l does not equal letter at r
word is not palindrome
else
increase l and decrease r
end
word is palindrome
于 2008-12-16T14:44:13.380 回答
0
这里没有一个解决方案考虑回文也可以基于单词单元，而不仅仅是字符单元。
这意味着对于像“女孩，穿着比基尼洗澡，盯着男孩，看到男孩在洗澡的女孩身上盯着比基尼”这样的回文，没有一个给定的解决方案是正确的。
这是 C# 中的一个 hacked together 版本。我确信它不需要正则表达式，但它与上述比基尼回文一样有效，就像它与“一个男人，一个计划，一条运河-巴拿马！”一样。
static bool IsPalindrome(string text)
{
bool isPalindrome = IsCharacterPalindrome(text);
if (!isPalindrome)
{
isPalindrome = IsPhrasePalindrome(text);
}
return isPalindrome;
}
static bool IsCharacterPalindrome(string text)
{
String clean = Regex.Replace(text.ToLower(), "[^A-z0-9]", String.Empty, RegexOptions.Compiled);
bool isPalindrome = false;
if (!String.IsNullOrEmpty(clean) && clean.Length > 1)
{
isPalindrome = true;
for (int i = 0, count = clean.Length / 2 + 1; i < count; i++)
{
if (clean[i] != clean[clean.Length - 1 - i])
{
isPalindrome = false; break;
}
}
}
return isPalindrome;
}
static bool IsPhrasePalindrome(string text)
{
bool isPalindrome = false;
String clean = Regex.Replace(text.ToLower(), @"[^A-z0-9\s]", " ", RegexOptions.Compiled).Trim();
String[] words = Regex.Split(clean, @"\s+");
if (words.Length > 1)
{
isPalindrome = true;
for (int i = 0, count = words.Length / 2 + 1; i < count; i++)
{
if (words[i] != words[words.Length - 1 - i])
{
isPalindrome = false; break;
}
}
}
return isPalindrome;
}
于 2008-10-23T06:16:55.893 回答
0
我还没有看到任何递归，所以这里......
import re
r = re.compile("[^0-9a-zA-Z]")
def is_pal(s):
def inner_pal(s):
if len(s) == 0:
return True
elif s[0] == s[-1]:
return inner_pal(s[1:-1])
else:
return False
r = re.compile("[^0-9a-zA-Z]")
return inner_pal(r.sub("", s).lower())
于 2008-11-04T21:05:13.710 回答
0
C#版本：
假设 MyString 是一个 char[]，方法在验证字符串后返回，它忽略空格和 <,>，但这可以扩展为忽略更多，可能实现忽略列表的正则表达式匹配。
public bool IsPalindrome()
if (MyString.Length == 0)
return false;
int len = MyString.Length - 1;
int first = 0;
int second = 0;
for (int i = 0, j = len; i <= len / 2; i++, j--)
{
while (i<j && MyString[i] == ' ' || MyString[i] == ',')
i++;
while(j>i && MyString[j] == ' ' || MyString[j] == ',')
j--;
if ((i == len / 2) && (i == j))
return true;
first = MyString[i] >= 97 && MyString[i] <= 122 ? MyString[i] - 32 : MyString[i];
second = MyString[j] >= 97 && MyString[j] <= 122 ? MyString[j] - 32 : MyString[j];
if (first != second)
return false;
}
return true;
}
快速测试用例
负 1. ABCDA 2. AB CBAG 3. A#$BDA 4. NULL/EMPTY
正面 1. ABCBA 2. A, man a plan a canal,,巴拿马 3. ABC BA 4. M 5. ACCB
让我知道任何想法/错误。
于 2010-05-01T22:14:01.277 回答
0
斯卡拉
def pal(s:String) = Symbol(s) equals Symbol(s.reverse)
于 2009-07-03T08:53:44.453 回答
0
public class palindrome {
public static void main(String[] args) {
StringBuffer strBuf1 = new StringBuffer("malayalam");
StringBuffer strBuf2 = new StringBuffer("malayalam");
strBuf2.reverse();
System.out.println(strBuf2);
System.out.println((strBuf1.toString()).equals(strBuf2.toString()));
if ((strBuf1.toString()).equals(strBuf2.toString()))
System.out.println("palindrome");
else
System.out.println("not a palindrome");
}
}
于 2013-02-08T12:45:48.077 回答
0
public bool IsPalindrome(string s)
{
string formattedString = s.Replace(" ", string.Empty).ToLower();
for (int i = 0; i < formattedString.Length / 2; i++)
{
if (formattedString[i] != formattedString[formattedString.Length - 1 - i])
return false;
}
return true;
}
这种方法适用于像“我看到的是老鼠吗”这样的刺痛。但我觉得我们需要通过正则表达式消除特殊字符。
于 2010-01-12T13:46:55.193 回答
0
public static boolean isPalindrome( String str ) {
int count = str.length() ;
int i, j = count - 1 ;
for ( i = 0 ; i < count ; i++ ) {
if ( str.charAt(i) != str.charAt(j) ) return false ;
if ( i == j ) return true ;
j-- ;
}
return true ;
}
于 2011-03-31T00:38:45.120 回答
0
一个不区分大小写、const友好的纯 C 语言版本，它忽略非字母数字字符（例如空格/标点符号）。因此，它实际上会传承经典，例如“一个人，一个计划，一条运河，巴拿马”。
int ispalin(const char *b)
{
const char *e = b;
while (*++e);
while (--e >= b)
{
if (isalnum(*e))
{
while (*b && !isalnum(*b)) ++b;
if (toupper(*b++) != toupper(*e)) return 0;
}
}
return 1;
}
于 2013-02-16T02:53:55.837 回答
0
//Single program for Both String or Integer to check palindrome
//In java with out using string functions like reverse and equals method also and display matching characters also
package com.practice;
import java.util.Scanner;
public class Pallindrome {
public static void main(String args[]) {
Scanner sc=new Scanner(System.in);
int i=0,j=0,k,count=0;
String input,temp;
System.out.println("Enter the String or Integer");
input=sc.nextLine();
temp=input;
k=temp.length()-1;
for(i=0;i<=input.length()-1;i++) {
if(input.charAt(j)==temp.charAt(k)) {
count++;
}
//For matching characters
j++;
k--;
}
System.out.println("Matching Characters = "+count);
if(count==input.length()) {
System.out.println("It's a pallindrome");
}
else {
System.out.println("It's not a pallindrome");
}
}
}
于 2014-07-15T13:21:33.017 回答
0
常规方法：
flag = True // Assume palindrome is true
for i from 0 to n/2
{ compare element[i] and element[n-i-1] // 0 to n-1
if not equal set flag = False
break }
return flag
有一种更好的机器优化方法，它使用 XOR，但具有相同的复杂性
XOR 方法：
n = length of string
mid_element = element[n/2 +1]
for i from 0 to n
{ t_xor = element[i] xor element[i+1] }
if n is odd compare mid_element and t_xor
else check t_xor is zero
于 2012-02-16T04:45:42.083 回答
0
这个 PHP 示例怎么样：
function noitcnuf( $returnstrrevverrtsnruter, $functionnoitcnuf) {
$returnstrrev = "returnstrrevverrtsnruter";
$verrtsnruter = $functionnoitcnuf;
return (strrev ($verrtsnruter) == $functionnoitcnuf) ;
}
于 2011-02-26T22:42:47.790 回答
0
如果您可以使用 Java API 和额外的存储：
public static final boolean isPalindromeWithAdditionalStorage(String string) {
String reversed = new StringBuilder(string).reverse().toString();
return string.equals(reversed);
}
In 可能需要 Java 的就地方法：
public static final boolean isPalindromeInPlace(String string) {
char[] array = string.toCharArray();
int length = array.length-1;
int half = Math.round(array.length/2);
char a,b;
for (int i=length; i>=half; i--) {
a = array[length-i];
b = array[i];
if (a != b) return false;
}
return true;
}
于 2012-01-04T20:30:01.793 回答
0
面试官会寻找一些关于你将如何解决这个问题的逻辑：请考虑以下 java 代码：
- 始终检查输入字符串是否为空
- 检查你的基本情况。
- 相应地格式化您的字符串（删除任何不是字符/数字的内容
- 他们很可能不想查看您是否知道反向函数和比较，而是希望您是否能够使用循环和索引来回答问题。
知道答案后立即返回，不要白白浪费资源。
公共静态布尔 isPalindrome(String s) {
if (s == null || s.length() == 0 || s.length() == 1) return false; String ss = s.toLowerCase().replaceAll("/[^a-z]/", ""); for (int i = 0; i < ss.length()/2; i++) if (ss.charAt(i) != ss.charAt(ss.length() - 1 - i)) return false; return true;}
于 2013-11-10T18:50:18.303 回答
0
// JavaScript Version.
function isPalindrome(str) {
str = str.replace(/[^a-zA-Z]/g, '')
return str.split('').reverse().join('').toUpperCase() === str.toUpperCase()
}
于 2015-09-13T13:42:37.897 回答