주어진 문자열이 회문인지 확인하는 방법은 무엇입니까?
정의:
회문은 어느 방향 으로든 같은 것을 읽는 속성을 가진 단어, 구, 숫자 또는 기타 단위 시퀀스입니다.
주어진 문자열이 회문인지 확인하는 방법은 무엇입니까?
이것은 얼마 전 FAIQ [자주 묻는 인터뷰 질문] 중 하나 였지만 주로 C를 사용했습니다.
가능한 모든 언어로 솔루션을 찾고 있습니다.
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 # 현재 위치 알고리즘. 이 함수로 전달하기 전에 대소 문자를 구분하지 않거나 공백 및 구두점 제거와 같은 모든 전처리를 수행해야합니다.
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 = "a b a";
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?모든 문자열을 호출 할 수 있습니다 .
최적화되지 않은 Python :
>>> def is_palindrome(s):
... return s == s[::-1]
자바 솔루션 :
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).
첫 번째 불일치까지 각 문자를 팝하고 비교하십시오.
스택에 요소가없는 경우 : 회문.
* 길이가 홀수 인 문자열의 경우 중간 문자를 버립니다.
집에 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을 반환하고 true와 false에 대해 0을 반환 할 수 있습니다.
여기에 파이썬 방식이 있습니다. 참고 : 이것은 실제로 "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;
여기에 오답이 많이 있습니다. 올바른 솔루션은 공백과 구두점 (그리고 실제로 알파벳이 아닌 문자)을 무시해야하며 대소 문자를 구분하지 않아야합니다.
몇 가지 좋은 예제 테스트 사례는 다음과 같습니다.
"남자, 계획, 운하, 파나마."
"토요타는 토요타 다."
"ㅏ"
""
일부 비 회문도 마찬가지입니다.
C #의 예제 솔루션 (참고 :이 디자인에서 빈 문자열과 null 문자열은 회문으로 간주되며, 원하지 않는 경우 변경하기 쉽습니다) :
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 ++ 방식.
우아한 반복자를 사용하는 순진한 구현. 실제로 순방향 반복기가 문자열의 중간 표시를 지나면 확인하고 중지 할 수 있습니다.
#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());
}
자바 버전
여기에 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;
}
다음은 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);
}
다음은 다양한 대소 문자, 구두점 및 공백을 다루는 Python 버전입니다.
import string
def is_palindrome(palindrome):
letters = palindrome.translate(string.maketrans("",""),
string.whitespace + string.punctuation).lower()
return letters == letters[::-1]
편집 : Blair Conrad의 깔끔한 답변 에서 뻔뻔스럽게 훔쳐 이전 버전에서 약간 서투른 목록 처리를 제거했습니다.
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
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"
루비:
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)
if (*left != *right)
return false;
return true;
}Lisp :
(defun palindrome(x) (string= x (reverse x)))
스몰 토크의 세 가지 버전, 멍청한 것부터 수정하는 것까지.
Smalltalk =에서 비교 연산자는 다음과 같습니다.
isPalindrome: aString
"Dumbest."
^ aString reverse = aString
메시지 #translateToLowercase는 문자열을 소문자로 반환합니다.
isPalindrome: aString
"Case insensitive"
|lowercase|
lowercase := aString translateToLowercase.
^ lowercase reverse = lowercase
그리고 스몰 토크에서 문자열은 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
위의 C ++ 솔루션에는 몇 가지 문제가 있습니다.
한 가지 해결책은 std :: string을 복사로 전달하고 문자의 절반 만 비교하는 대신 모든 문자를 반복했기 때문에 비효율적이었습니다. 그런 다음 문자열이 회문이 아님을 발견하더라도 "거짓"을보고하기 전에 끝을 기다리면서 루프를 계속했습니다.
다른 하나는 매우 작은 함수로 더 좋았습니다. 문제는 std :: string 이외의 다른 것을 테스트 할 수 없다는 것입니다. C ++에서는 알고리즘을 유사한 객체 전체로 쉽게 확장 할 수 있습니다. std :: string을 "T"로 템플릿 화하면 std :: string, std :: wstring, std :: vector 및 std :: deque 모두에서 작동했을 것입니다. 그러나 <연산자를 사용하기 때문에 큰 수정없이 std :: list는 범위를 벗어났습니다.
내 솔루션은 C ++ 솔루션이 정확한 현재 유형에서 작동하는 것을 멈추지 않고 유형에 관계없이 동일한 방식 으로 작동하는 모든 작업을 수행하려고 노력 합니다. 예를 들어, Anything이 연산자 = (유형 및 클래스 빌드)를 통해 비교할 수있는 한 std :: string, int 벡터 또는 "Anything"목록에 회문 테스트를 적용 할 수 있습니다.
데이터를 비교하는 데 사용할 수있는 선택적 유형으로 템플릿을 확장 할 수도 있습니다. 예를 들어 대소 문자를 구분하지 않고 비교하거나 유사한 문자 (예 : è, é, ë, ê 및 e)를 비교하려는 경우입니다.
Leonidas 왕이 말했듯 이 "템플릿? 이것은 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!
It will work with almost any unordered STL-like container with bidirectional iterators For example, any std::basic_string, std::vector, std::deque, std::list, etc. So, this function can be applied on all STL-like containers with the following conditions: 1 - T is a container with bidirectional iterator 2 - T's iterator points to a comparable type (through 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 ;
}
}
A simple Java solution:
public boolean isPalindrome(String testString) {
StringBuffer sb = new StringBuffer(testString);
String reverseString = sb.reverse().toString();
if(testString.equalsIgnoreCase(reverseString)) {
return true;
else {
return false;
}
}
Many ways to do it. I guess the key is to do it in the most efficient way possible (without looping the string). I would do it as a char array which can be reversed easily (using 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");
}
In Ruby, converting to lowercase and stripping everything not alphabetic:
def isPalindrome( string )
( test = string.downcase.gsub( /[^a-z]/, '' ) ) == test.reverse
end
But that feels like cheating, right? No pointers or anything! So here's a C version too, but without the lowercase and character stripping goodness:
#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;
}
Well, that was fun - do I get the job ;^)
Using Java, using Apache Commons String Utils:
public boolean isPalindrome(String phrase) {
phrase = phrase.toLowerCase().replaceAll("[^a-z]", "");
return StringUtils.reverse(phrase).equals(phrase);
}
ReferenceURL : https://stackoverflow.com/questions/52002/how-to-check-if-the-given-string-is-palindrome
'programing' 카테고리의 다른 글
| NSString에서 하위 문자열의 발생 횟수? (0) | 2020.12.26 |
|---|---|
| 산술 연산자를 사용하여 0과 1 사이를 뒤집을 수 있습니까? (0) | 2020.12.26 |
| xlwt를 사용하여 기존 통합 문서에 쓰기 (0) | 2020.12.26 |
| phpmyadmin.pma_table_uiprefs가 존재하지 않습니다. (0) | 2020.12.26 |
| 자연어와 가장 유사한 프로그래밍 언어는 무엇입니까? (0) | 2020.12.26 |