定义：
回文词是单词，词组，数字或其他单位序列，具有沿任一方向读取相同内容的特性
如何检查给定的字符串是否是回文？
这是前一段时间的FAIQ(常见访谈问题)之一，但大部分使用C。
寻找任何可能的语言解决方案。
PHP示例：
1
2
3
4
5
6
7
| $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脚本：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
| @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 |
语言不可知元代码然后...
1
2
| rev = StringReverse(originalString)
return ( rev == originalString ); |
C＃就地算法。在传递给该函数之前，应进行任何预处理，例如不区分大小写或去除空格和标点符号。
1
2
3
4
5
6
7
| 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"，并将保存的比较用于删除冗余的Length比较。感谢评论者！
C＃：LINQ
1
2
3
| var str ="a b a";
var test = Enumerable.SequenceEqual(str.ToCharArray(),
str.ToCharArray().Reverse()); |
Hal的Ruby版本的更Ruby风格的重写：
1
2
3
4
5
| class String
def palindrome?
(test = gsub(/[^A-Za-z]/, '').downcase) == test.reverse
end
end |
现在您可以在任何字符串上调用palindrome?。
Java解决方案：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
| 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!");
} |
}
未优化的Python：
1
2
| >>> def is_palindrome(s):
... return s == s[::-1] |
使用良好的数据结构通常会给教授留下深刻的印象：
将一半的字符推入堆栈(长度/ 2)。
弹出并比较每个字符，直到第一个不匹配。
如果堆栈中的元素为零：回文。
*对于长度为奇数的字符串，请丢弃中间的字符。
C在房子里。 (不确定您是否不想在这里使用C示例)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
| 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。
这是一种python方式。注意：这并不是真正的" pythonic"，但它演示了该算法。
1
2
3
4
5
6
7
8
| 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 |
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
| 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; |
编辑：从评论：
1
2
3
4
| bool palindrome(std::string const& s)
{
return std::equal(s.begin(), s.end(), s.rbegin());
} |
C ++方式。
我朴素的实现使用优雅的迭代器。实际上，您可能会检查
并在您的前向迭代器超过字符串的一半时停止。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
| #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;
} |
我在这里看到很多错误的答案。任何正确的解决方案都需要忽略空格和标点符号(实际上是任何非字母字符)，并且不区分大小写。
一些好的示例测试用例是：
"一个人，一个计划，一条运河，巴拿马。"
"丰田就是丰田。"
"一种"
"
以及一些非回文症。
C＃中的示例解决方案(注意：在此设计中，空字符串和空字符串被视为回文，如果不希望这样做，很容易更改)：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
| 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;
} |
1
2
3
4
5
| 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版本
这是处理不同情况，标点符号和空格的Python版本。
1
2
3
4
5
6
| import string
def is_palindrome(palindrome):
letters = palindrome.translate(string.maketrans("",""),
string.whitespace + string.punctuation).lower()
return letters == letters[::-1] |
编辑：无耻地偷走了布莱尔·康拉德(Blair Conrad)的整洁答案，从我以前的版本中删除了稍微笨拙的列表处理。
这是我的解决方案，无需使用strrev。用C＃编写，但是它可以在任何具有字符串长度功能的语言中使用。
1
2
3
4
5
6
7
8
| 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;
} |
混淆的C版本：
1
2
3
4
5
6
| 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;
} |
C ++
1
2
3
4
5
| std::string a ="god";
std::string b ="lol";
std::cout << (std::string(a.rbegin(), a.rend()) == a) <<""
<< (std::string(b.rbegin(), b.rend()) == b); |
巴什
1
2
| function ispalin { ["$( echo -n $1 | tac -rs . )" ="$1" ]; }
echo"$(ispalin god && echo yes || echo no), $(ispalin lol && echo yes || echo no)" |
古努·阿克(Gnu Awk)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
| /* 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中一些脑筋急转弯的方式
1
2
| 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"
红宝石：
1
2
3
4
5
6
7
8
9
10
| 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＃中的解决方案
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
| 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);
} |
请注意，在上述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通过其operator =(可在类型以及类中进行构建)进行比较即可。
请注意，甚至可以使用可用于比较数据的可选类型扩展模板。例如，如果您想以不区分大小写的方式进行比较，或者甚至比较相似的字符(例如è，é，？，ê和e)。
就像列奥尼达斯国王会说："模板？这是C ++ ！！！"
因此，在C ++中，至少有3种主要方法可以做到这一点，每种方法都可以导致另一种方法：
解决方案A：采用类似C的方式
问题在于，直到C ++ 0X，我们才能将char的std :: string数组视为连续的，因此我们必须"作弊"并检索c_str()属性。由于我们以只读方式使用它，因此应该可以...
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
| 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 []是对这些容器的恒定访问，因此我们不会损失不必要的速度。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
| 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 =)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
| 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 ;
}
} |
Lisp的：
1
| (defun palindrome(x) (string= x (reverse x))) |
从最笨拙到正确的Smalltalk中的三个版本。
在Smalltalk中，=是比较运算符：
1
2
3
| isPalindrome: aString
"Dumbest."
^ aString reverse = aString |
消息#translateToLowercase返回字符串为小写字母：
1
2
3
4
5
| isPalindrome: aString
"Case insensitive"
|lowercase|
lowercase := aString translateToLowercase.
^ lowercase reverse = lowercase |
在Smalltalk中，字符串是Collection框架的一部分，您可以使用消息#select:thenCollect:，所以这是最后一个版本：
1
2
3
4
5
6
7
8
| 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 |
此Java代码应在布尔方法内工作：
注意：您只需要检查字符的前半部分和后半部分，否则您将需要进行的检查数量重叠和加倍。
1
2
3
4
5
6
7
8
| 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 ++。针对速度和大小进行了优化。
一个简单的Java解决方案：
1
2
3
4
5
6
7
8
9
10
| public boolean isPalindrome(String testString) {
StringBuffer sb = new StringBuffer(testString);
String reverseString = sb.reverse().toString();
if(testString.equalsIgnoreCase(reverseString)) {
return true;
else {
return false;
}
} |
我的2c。避免每次都发生完全字符串反转的开销，并在确定字符串性质后立即利用短路返回。是的，您应该先对字符串进行条件设置，但是IMO就是另一个函数的工作。
在C＃中
1
2
3
4
5
6
7
8
9
10
11
12
| /// <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;
} |
简单的JavaScript解决方案。运行演示代码段。
1
2
3
4
5
| function checkPalindrome(line){
reverse_line=line.split("").reverse().join("");
return line==reverse_line;
}
alert("checkPalindrome(radar):"+checkPalindrome("radar")); |
有很多方法可以做到。我猜关键是要以最有效的方式做到这一点(不循环字符串)。我会将其作为可以很容易地反转(使用C＃)的char数组进行。
1
2
3
4
5
6
7
8
9
10
| 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");
} |
还没有使用JavaScript的解决方案吗？
1
2
3
4
5
| function palindrome(s) {
var l = 0, r = s.length - 1;
while (l < r) if (s.charAt(left++) !== s.charAt(r--)) return false;
return true
} |
Erlang很棒
1
2
3
4
5
6
7
| palindrome(L) -> palindrome(L,[]).
palindrome([],_) -> false;
palindrome([_|[]],[]) -> true;
palindrome([_|L],L) -> true;
palindrome(L,L) -> true;
palindrome([H|T], Acc) -> palindrome(T, [H|Acc]). |
Prolog
1
2
3
4
5
6
| palindrome(B, R) :-
palindrome(B, R, []).
palindrome([], R, R).
palindrome([X|B], [X|R], T) :-
palindrome(B, R, [X|T]). |
Perl的：
1
2
3
4
5
| sub is_palindrome {
my $s = lc shift; # normalize case
$s =~ s/\W//g; # strip non-word characters
return $s eq reverse $s;
} |
在Ruby中，转换为小写并剥离所有非字母的内容：
1
2
3
| def isPalindrome( string )
( test = string.downcase.gsub( /[^a-z]/, '' ) ) == test.reverse
end |
但这感觉就像在作弊，对吗？没有指针或任何东西！因此，这也是C版本，但没有小写字母和字符剥离优点：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
| #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>
", argv[0] );
return -1;
}
fprintf( stdout,"%s
", isPalindrome( argv[1] ) ?"yes" :"no" );
return 0;
} |
好吧，那很有趣-我能得到这份工作吗？
Perl的：
1
2
3
4
5
6
| sub is_palindrome($)
{
$s = lc(shift); # ignore case
$s =~ s/\W+//g; # consider only letters, digits, and '_'
$s eq reverse $s;
} |
它忽略大小写并去除非字母数字字符(其语言环境和Unicode中性)。
使用Java，使用Apache Commons String Utils：
1
2
3
4
| public boolean isPalindrome(String phrase) {
phrase = phrase.toLowerCase().replaceAll("[^a-z]","");
return StringUtils.reverse(phrase).equals(phrase);
} |
我不得不这样做是为了应对编程挑战，这是我的Haskell的摘要：
1
2
| isPalindrome :: String -> Bool
isPalindrome n = (n == reverse n) |
Python：
1
| if s == s[::-1]: return True |
Java的：
1
| if (s.Equals(s.Reverse())) { return true; } |
PHP：
1
| if (s == strrev(s)) return true; |
Perl的：
1
| if (s == reverse(s)) { return true; } |
二郎：
1
| string:equal(S, lists:reverse(S)). |
C ++：
1
2
3
4
| bool is_palindrome(const string &s)
{
return equal( s.begin(), s.begin()+s.length()/2, s.rbegin());
} |
C＃版本：
假设MyString是char []，方法在验证字符串后返回，它忽略空格和<，>，但是可以扩展为忽略更多，可能实现忽略列表的正则表达式匹配。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
| 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.空/空
正
1. ABCBA
2.一个人计划一条运河，巴拿马
3. ABC BA
4. M
5. ACCB
让我知道任何想法/错误。
1
2
3
| public static boolean isPalindrome(String str) {
return str.equals(new StringBuilder(str).reverse().toString());
} |
对于Java低于1.5的版本，
1
2
3
| public static boolean isPalindrome(String str) {
return str.equals(new StringBuffer().append(str).reverse().toString());
} |
要么
1
2
3
4
5
6
7
8
9
10
11
12
| 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;
} |
剔除不在A-Z或a-z之间的任何字符的解决方案以英语为中心。带有变音符号(例如à或é)的字母将被删除！
根据维基百科：
The treatment of diacritics varies. In languages such as Czech and Spanish, letters with diacritics or accents (except tildes) are not given a separate place in the alphabet, and thus preserve the palindrome whether or not the repeated letter has an ornamentation. However, in Swedish and other Nordic languages, A and A with a ring (?) are distinct letters and must be mirrored exactly to be considered a true palindrome.
因此，要覆盖许多其他语言，最好使用归类将变音符号转换为等效的非变音符号，或者适当地保留它们，然后仅在比较之前去除空格和标点符号。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
| //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");
}
}
} |
带有堆栈的Java。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
| 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!""));
} |
面试官将寻找有关您如何解决此问题的逻辑：
请考虑以下Java代码：
始终检查输入字符串是否为null
检查您的基本情况。
相应地格式化字符串(删除所有非字符/数字的字符
最有可能的是，他们不希望看到您是否知道反向函数以及进行比较，而是希望您能够使用循环和索引来回答问题。
您知道答案后立即返回快捷方式，不要浪费资源。
公共静态布尔isPalindrome(String s){
1
2
3
4
5
6
7
8
9
| 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; |
}
普通C语言中不区分大小写且const友好的版本，它将忽略非字母数字字符(例如，空格/标点符号)。因此，它实际上会传递"一个人，一个计划，一条运河，巴拿马"之类的经典作品。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
| 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;
} |
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
| 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");
}
} |
高效的C ++版本：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
| 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;
} |
常规方法：
1
2
3
4
5
6
| 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方法：
1
2
3
4
5
6
| 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 |
如果可以使用Java API和其他存储：
1
2
3
4
| public static final boolean isPalindromeWithAdditionalStorage(String string) {
String reversed = new StringBuilder(string).reverse().toString();
return string.equals(reversed);
} |
中可能需要Java的就地方法：
1
2
3
4
5
6
7
8
9
10
11
12
| 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;
} |
这一切都很好，但是有没有办法在算法上做得更好？曾经在一次采访中要求我认识线性时间和恒定空间中的回文。
那时我什么也想不出来，现在仍然不会。
(如果有帮助，我问面试官答案是什么。他说，您可以构造一对哈希函数，以便仅当该字符串是回文时，才可以将给定的字符串哈希为相同的值。我不知道该怎么做。您实际上会做这对功能。)
我还没有看到任何递归，所以这里...
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
| 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()) |
斯卡拉
1
| def pal(s:String) = Symbol(s) equals Symbol(s.reverse) |
这个PHP示例如何：
1
2
3
4
5
| function noitcnuf( $returnstrrevverrtsnruter, $functionnoitcnuf) {
$returnstrrev ="returnstrrevverrtsnruter";
$verrtsnruter = $functionnoitcnuf;
return (strrev ($verrtsnruter) == $functionnoitcnuf) ;
} |
OCaml的：
1
2
| let rec palindrome s =
s = (tailrev s) |
资源
来自Delphi的另一篇文章，我认为它比提交的其他Delphi示例更加严格。这很容易变成高尔夫比赛，但我试图使我的可读性。
Edit0：我对性能特征很好奇，所以做了一些测试。在我的机器上，我对60个字符串运行了此功能5000万次，这花了5秒钟。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
| 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＃中，这是同一件事，除了我给它留了多个我不喜欢的出口点。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
| 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;
} |
C＃3-从头算起的char与末尾的等价字符不匹配时，此方法立即返回false：
1
2
3
4
5
6
7
8
9
10
11
| 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;
} |
1
2
3
4
5
6
7
8
9
10
| 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;
} |
这种方法适用于像"我看见它是只老鼠"那样的刺痛。但是我觉得我们需要通过正则表达式消除特殊字符。
这里没有一个单一的解决方案考虑到回文也可以基于单词单位，而不仅仅是字符单位。
这意味着给定的解决方案都不会对回文式如"女孩，在比基尼上洗澡，盯着男孩，看到男孩在比基尼上盯着女孩穿比基尼"的回文中。
这是C＃中的共同入侵版本。我确定它不需要正则表达式，但是它对于上述比基尼回文和"男人，计划，运河巴拿马！"同样有效。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
| 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;
} |
1
2
3
4
5
| // JavaScript Version.
function isPalindrome(str) {
str = str.replace(/[^a-zA-Z]/g, '')
return str.split('').reverse().join('').toUpperCase() === str.toUpperCase()
} |
1
2
3
4
5
6
7
8
9
10
11
| 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 |
这是另外两个Perl版本，两个都不使用reverse。两者都使用将字符串的第一个字符与最后一个字符进行比较，然后将其丢弃并重复测试的基本算法，但是它们使用不同的方法来获得各个字符(第一个字符使用正则表达式一次剥离一个，第二个split将字符串转换为字符数组)。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
| #!/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)
"
:"'$string' is not a palindrome (1)
";
print is_palindrome2($string) ?"'$string' is a palindrome (2)
"
:"'$string' is not a palindrome (2)
";
}
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;
} |
const正确的C / C ++指针解决方案。循环中的最少操作。
1
2
3
4
5
6
7
8
9
| 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;
} |
C＃中的简易模式，仅使用基类库
编辑：刚刚看到有人做了Array.Reverse也
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
| 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;
} |
1
2
3
| boolean IsPalindrome(string s) {
return s = s.Reverse();
} |
如果我们正在寻找数字和简单的单词，则给出了许多正确的答案。
但是，如果我们要寻找书面语言中通常称为回文的事物(例如，"狗，恐慌，在宝塔中！")，则正确的答案是从句子的两端开始迭代，跳过非字母数字字符，如果发现不匹配，则返回false。
1
2
3
4
5
6
7
8
9
10
11
| 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--;
} |
当然，去除无效字符，反转结果字符串并将其与原始字符串进行比较也可以。这取决于您正在使用哪种语言。
这是我在执行示例服务器控件时使用的另一个C＃代码。可以在ASP.NET 3.5 Step by Step(MS Press)一书中找到。这是两种方法，一种剥离非字母数字，另一种检查回文。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
| 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;
}
} |
1
2
3
4
5
6
7
8
9
10
| 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 ;
} |
