pra*_*ash 56 language-agnostic string
定义:
回文是单词,短语,数字或其他单元序列,具有在任一方向上读取相同的属性
如何检查给定的字符串是否是回文？
这是前一段时间的FAIQ [常见问题访谈问题]之一,但主要是使用C.
寻找任何和所有语言的解决方案.
Con*_*oyP 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);
}
删除任何非字母数字字符(空格,逗号,感叹号等),以允许如上所述的完整句子,以及简单的单词.
Pau*_*ius 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
Tni*_*son 29
然后语言不可知的元代码......
rev = StringReverse(originalString)
return ( rev == originalString );
Dav*_*itt 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在循环条件中删除不必要的" ",并在删除冗余长度比较时花费了已保存的比较.感谢评论者!
aku*_*aku 15
C#:LINQ
var str = "a b a";
var test = Enumerable.SequenceEqual(str.ToCharArray(),
str.ToCharArray().Reverse());
Bri*_*haw 14
更多Ruby风格的Hal的Ruby版本重写:
class String
def palindrome?
(test = gsub(/[^A-Za-z]/, '').downcase) == test.reverse
end
end
现在你可以调用palindrome?任何字符串.
Bla*_*rad 11
未经优化的Python:
>>> def is_palindrome(s):
... return s == s[::-1]
Jon*_*han 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!");
}
}
xan*_*ont 10
使用良好的数据结构通常会给教授留下深刻的印象:
将一半字符推入堆栈(长度/ 2).
弹出并比较每个char直到第一个不匹配.
如果堆栈元素为零:回文结构.
*如果字符串具有奇数长度,则抛出中间字符.
Hos*_*ile 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;
}
对于"赛车","赛车","赛车","赛车"和"RaCe cAr",这将成为现实.修改包含符号或空格也很容易,但我认为仅计算字母(并忽略大小写)更有用.这适用于我在答案中找到的所有回文,我一直无法将其欺骗为假阴性/阳性.
另外,如果你不喜欢"C"程序中的bool,它显然可以返回int,返回1并分别返回0表示true和false.
这是一种蟒蛇的方式.注意:这不是真正的"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
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;
编辑:从评论:
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;
}
我在这里看到了很多不正确的答案.任何正确的解决方案都需要忽略空格和标点符号(实际上是任何非字母字符),并且需要不区分大小写.
一些很好的示例测试用例是:
"一个男人,一个计划,一条运河,巴拿马."
"丰田是一辆丰田汽车."
"一个"
""
以及一些非回文.
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;
}
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版本