수년 동안 문자열이 회문인지 아닌지 확인하는 것은 고전적인 코딩 인터뷰 질문이되었습니다. 이는 문자열 조작 및 비교에 대한 개념과 구현에 따라 루프까지 포함하기 때문입니다. 그리고 질문은 긴 질문이 아니므로 인터뷰 시간 내에 완료 할 수 있습니다. 이 기사에는 자바와 파이썬에서 문자열이 회문인지 확인하는 구현이 포함되어 있습니다.
회문이란 무엇입니까?
synonym.com에 따르면 회 문의 정의는 "앞쪽과 같은 뒤쪽으로 읽는 단어 또는 구"입니다. 기본적으로 단어 나 구를 반대로 쓰면 앞으로 올 때와 똑같다는 뜻입니다. 예를 들어, 아빠와 엄마는 회문이고 아버지와 엄마는 그렇지 않습니다. "palindrome"이라는 단어는 두 개의 그리스어 어근에서 유래했습니다. "palin"은 다시 의미하고 "dromos"는 방법이나 방향을 의미합니다. 17 세기에 영국 극작가 벤 존슨이 만들었습니다.
해결책
- 문제를 해결하는 가장 일반적이고 쉬운 방법은 먼저 문자열을 뒤집은 다음 원래 문자열과 비교하는 것입니다. 이 접근법은 문자열 반전이 O (n)이기 때문에 big-O 표기법에서 O (n)입니다.
- 또 다른 방법은 처음부터 끝까지 문자 비교를 시작하고 중간에 도달 할 때까지 계속하는 것입니다. 이 접근 방식은 O (n / 2)의 시간 복잡도를 갖지만 big-O 표기법에서는 여전히 O (n)입니다. 그러나이 접근 방식의 장점은 첫 번째 불일치가 발생하자마자 False를 반환 할 수 있다는 점입니다. 반면 첫 번째 접근 방식에서는 문자열 반전이 첫 번째 단계이므로 시간 복잡도는 항상 O (n)입니다.
파이썬 구현의 회문
다음은 파이썬에서 문자열이 회문인지 확인하는 코드입니다.
def is_palindrome (s) : "" "주어진 인수 s가 회문이면 True를 반환합니다. 그렇지 않으면 False" ""assert (isinstance (s, str)), "Argument s가 유형이 아닙니다. "# 주어진 인수가 유형인지 확인 return s [::-1] == s # __name __ == "__ main__": print (is_palindrome ( "dad")) 인 경우 문자열의 반대를 자신과 비교합니다. def is_palindrome (word) : "" "문자를 처음부터 끝까지 하나씩 비교하고 첫 번째 불일치가 발생하면 False를 반환하거나 그렇지 않으면 True를 반환합니다." ""i1, i2 = 0, len (word) -1 # 초기화 커서가있는 동안 i2> i1 : if word [i1]! = word [i2] : # 문자가 일치하지 않으면 더 이상 진행할 필요가 없습니다 return False i1 + = 1 i2- = 1 return True if __name __ == "__ main__ ": print (is_palindrome ("아빠 ")) 자바 구현의 회문
다음은 자바에서 문자열이 회문인지 확인하는 코드입니다.
공개 클래스 Palindrome {공개 정적 부울 isPalindrome (String str) {StringBuilder sb = new StringBuilder (str); // StringBuilder에는 리버스 메소드가 있습니다. return sb.reverse (). toString (). equals (str); // 문자열의 반대를 자신과 비교} public static void main (String args []) {Boolean b = isPalindrome ( "dad"); System.out.println (b); }}public class Palindrome {public static Boolean isPalindrome (String str) {int i1 = 0; int i2 = str.length ()-1; while (i2> i1) {if (str.charAt (i1)! = str.charAt (i2)) {return false; } i1 ++; i2--; } return true; } public static void main (String args []) {Boolean b = isPalindrome ( "dad"); System.out.println (b); }} 
