문자열이 회문인지 확인하는 JAVA 프로그램 - TECHCODEVIEW.COM

문자열을 왼쪽에서 오른쪽으로 또는 오른쪽에서 왼쪽으로 읽기 시작하면 문자열이 동일하면 회문이라고 합니다. 이번 글에서는 자바에서 문자열이 회문인지 확인하는 방법을 배워보겠습니다.

그럼 문자열을 생각해 봅시다 str , 이제 작업은 역방향 문자열이 그대로인지 알아내는 것입니다.

회문의 예:

입력: str = 아바
산출: 예

입력: str = 괴짜
산출: 아니요

Java의 Palindrome 문자열에 대한 방법

아래와 같이 Java에서 문자열 회문을 확인하는 세 가지 주요 방법이 있습니다.

순진한 방법
두 포인터 방법
재귀적 방법
스트링빌더 사용

1. Java에서 Palindrome 문자열을 확인하는 순진한 접근 방식

주어진 문자열을 뒤집어서 비교합니다. 원래 문자열과 반대 버전을 비교하여 주어진 문자열이 회문인지 확인할 수 있습니다.

다음은 위의 접근 방식을 구현한 것입니다.

자바

  // Java Program to implement // Basic Approach to check if // string is a Palindrome import java.io.*; // Driver Class class GFG { // main function public static boolean isPalindrome(String str) { // Initializing an empty string to store the reverse // of the original str String rev = ''; // Initializing a new boolean variable for the // answer boolean ans = false; for (int i = str.length() - 1; i>= 0; i--) { rev = rev + str.charAt(i); } // 두 문자열이 모두 같은지 확인합니다. if (str.equals(rev)) { ans = true; } 답변을 반환합니다; } public static void main(String[] args) { // 입력 문자열 String str = 'geeks'; // 문자열을 소문자로 변환 str = str.toLowerCase(); 부울 A = isPalindrome(str); System.out.println(A); } }

산출

false

위 방법의 복잡성:

시간 복잡도: 주어진 코드의 시간 복잡도는 O(n)입니다. 여기서 n은 입력 문자열의 길이입니다. 이는 for 루프가 문자열의 각 문자를 한 번 반복하여 역방향 문자열을 생성하기 때문입니다.

공간 복잡도: 코드의 공간 복잡도는 O(n)입니다. 여기서 n은 입력 문자열의 길이입니다. 이는 역방향 문자열이 생성되어 별도의 문자열 변수에 저장되기 때문인데, 이는 입력 문자열의 길이에 비례하여 메모리 공간을 차지합니다. 또한 코드에 사용된 다른 변수(i, str 및 ans)는 입력 크기와 관계없이 일정한 공간을 차지합니다.

위의 예에서 다음과 같이 쓰면 아바 대신에 아바 , 그러면 다음과 같이 출력을 얻어야 합니다. 예 . 따라서 회문인지 확인하기 전에 문자열의 대소문자를 소문자 또는 대문자로 변경해야 합니다. 그렇게 하지 않으면 예상치 못한 결과를 얻게 될 것입니다. 이는 컴파일러가 해당 문자를 기반으로 문자를 확인하기 때문입니다. 아스키 가치와 아스키 가치 ㅏ 와 동일하지 않습니다 ㅏ .

2. P에 대한 두 포인터 접근 방식 Java의 alindrome 프로그램

우리의 접근 방식은 먼저 문자열을 소문자로 변환하는 것입니다. 그런 다음 두 가지 포인터를 사용하겠습니다. 나 문자열의 시작을 가리키는 제이 문자열의 끝을 가리킨다. 계속 증가 나 그리고 감소 제이 ~하는 동안 나 그리고 모든 단계에서 이 포인터의 문자가 동일한지 여부를 확인하십시오. 그렇지 않다면 문자열은 회문이 아니며 그렇지 않으면 회문입니다.

예시 1:
자바 // Java program to check whether a // string is a Palindrome // Using two pointing variables // Main class public class GFG { // Method // Returning true if string is palindrome static boolean isPalindrome(String str) { // Pointers pointing to the beginning // and the end of the string int i = 0, j = str.length() - 1; // While there are characters to compare while (i < j) { // If there is a mismatch if (str.charAt(i) != str.charAt(j)) return false; // Increment first pointer and // decrement the other i++; j--; } // Given string is a palindrome return true; } // Method 2 // main driver method public static void main(String[] args) { // Input string String str = 'geeks'; // Convert the string to lowercase str = str.toLowerCase(); // passing bool function till holding true if (isPalindrome(str)) // It is a palindrome System.out.print('Yes'); else // Not a palindrome System.out.print('No'); } }
산출
No

위 방법의 복잡성:

시간 복잡도: 주어진 코드의 시간 복잡도는 O(n)입니다. 여기서 n은 입력 문자열의 길이입니다. 이는 while 루프가 문자열의 절반을 반복하여 회문인지 확인하기 때문입니다. 문자열의 절반만 검사하므로 반복 횟수는 n/2, 즉 O(n)에 비례합니다.

공간 복잡도: 코드의 공간 복잡도는 O(1)입니다. 코드는 입력 크기와 관계없이 일정한 양의 추가 공간만 사용하기 때문입니다. 코드에 사용된 유일한 변수는 i, j 및 str이며, 각각은 일정한 양의 공간을 차지합니다. 코드에 추가 공간이 생성되지 않습니다.

예시 2:
자바 // Java Program to check Whether // the String is Palindrome // or Not // Main class class GFG { // Method 1 // Returns true if string is a palindrome static boolean isPalindrome(String str) { // Pointers pointing to the beginning // and the end of the string int i = 0, j = str.length() - 1; // While there are characters to compare while (i < j) { // If there is a mismatch if (str.charAt(i) != str.charAt(j)) return false; // Increment first pointer and // decrement the other i++; j--; } // Given string is a palindrome return true; } // Main driver method public static void main(String[] args) { String str = 'geeks'; String str2 = 'RACEcar'; // Change strings to lowercase str = str.toLowerCase(); str2 = str2.toLowerCase(); // For string 1 System.out.print('String 1 :'); if (isPalindrome(str)) System.out.print('It is a palindrome'); else System.out.print('It is not a palindrome'); // new line for better readability System.out.println(); // For string 2 System.out.print('String 2 :'); if (isPalindrome(str2)) System.out.print('It is a palindrome'); else System.out.print('It is not a palindrome'); } }
산출
String 1 :It is not a palindrome String 2 :It is a palindrome

위 방법의 복잡성:

시간 복잡도: 주어진 코드의 시간 복잡도는 O(n)입니다. 여기서 n은 입력 문자열의 길이입니다. 이는 `isPalindrome` 메서드의 while 루프가 문자열의 절반을 반복하여 회문인지 확인하기 때문입니다. 문자열의 절반만 검사하므로 반복 횟수는 n/2, 즉 O(n)에 비례합니다.

공간 복잡도: 코드의 공간 복잡도는 O(1)입니다. 코드는 입력 크기와 관계없이 일정한 양의 추가 공간만 사용하기 때문입니다. 코드에 사용된 유일한 변수는 i, j, str 및 str2이며, 각각은 일정한 양의 공간을 차지합니다. 코드에 추가 공간이 생성되지 않습니다.

3. P에 대한 재귀적 접근 Java의 alindrome 프로그램

접근 방식은 매우 간단합니다. 두 포인터 접근 방식과 마찬가지로 문자열의 첫 번째 값과 마지막 값을 확인하지만 이번에는 재귀를 통해 확인합니다.

문자열의 시작을 가리키는 두 개의 포인터 i와 문자열의 끝을 가리키는 j를 사용합니다.

i를 계속 증가시키고 j를 감소시키는 동안 i

이 포인터의 문자가 동일한지 여부를 확인하십시오. 우리는 재귀를 통해 이를 수행합니다 – (i+1, j-1

i>=j 조건이 만족될 때까지 i번째와 j번째 인덱스의 모든 문자가 동일하면 true, else false를 인쇄합니다.

다음은 위의 접근 방식을 구현한 것입니다.
자바 // Java program to check whether a // string is a Palindrome using recursion import java.io.*; // Driver Class class GFG { public static boolean isPalindrome(int i, int j, String A) { // comparing the two pointers if (i>= j) { 참을 반환; } // 해당 포인터의 문자를 비교합니다. if (A.charAt(i) != A.charAt(j)) { return false; } // 모든 것을 다시 재귀적으로 검사 return isPalindrome(i + 1, j - 1, A); } public static boolean isPalindrome(String A) { return isPalindrome(0, A.length() - 1, A); } // 주요 함수 public static void main(String[] args) { // 입력 문자열 String A = 'geeks'; // 문자열을 소문자로 변환 A = A.toLowerCase(); 부울 str = isPalindrome(A); System.out.println(str); } }
산출
false

위 방법의 복잡성:

시간 복잡도: 주어진 코드의 시간 복잡도는 O(n)입니다. 여기서 n은 입력 문자열의 길이입니다. 이는 `isPalindrome` 함수가 포인터 i와 j가 서로 교차하거나 포인터의 문자가 동일하지 않을 때까지 (i+1, j-1) 위치의 문자를 반복적으로 호출하기 때문입니다. 문자열의 각 문자를 정확히 한 번씩 비교하므로 시간 복잡도는 O(n)입니다.

공간 복잡도: 코드의 공간 복잡도는 O(n)입니다. 여기서 n은 입력 문자열의 길이입니다. 이는 각 재귀 호출이 함수 매개변수와 지역 변수의 현재 값을 저장하는 새로운 스택 프레임을 생성하기 때문입니다. 최악의 경우 함수 호출 스택이 n/2(입력 문자열이 회문인 경우)만큼 커질 수 있으므로 공간 복잡도는 O(n)입니다.

4. Java에서 StringBuilder 접근 방식 사용

이 접근 방식에서는

먼저 사용자로부터 문자열 입력을 받습니다.

그런 다음 Stringbuilder 개체 str1″을 만들고 여기에 String 값을 저장합니다.

Stringbuider의 reverse() 메소드는 역방향 문자열을 제공합니다. 역 문자열을 str1에 저장하세요.

equals() 메소드를 사용하여 문자열 값을 비교하고 if 및 else 조건을 사용하여 문자열 값이 유사한지 여부를 확인합니다.

다음은 위의 접근 방식을 구현한 것입니다.
자바 import java.util.Scanner; public class Main { public static void main(String[] args) { String str = 'GeeksForGeeks'; // String for testing StringBuilder str1 = new StringBuilder(str); str1.reverse(); if (str.equals(str1.toString())) { System.out.println('Palindrome String'); } else { System.out.println('Not a palindrome String'); } } }
산출
Not a palindrome String

위 코드의 복잡성:

시간 복잡도: 코드의 시간 복잡도는 O(n)입니다. 여기서 n은 다시 입력 문자열 str의 길이입니다. 이 시간 복잡도에 영향을 미치는 주요 요인은 str1.reverse()를 사용하여 문자열을 반전시키는 것입니다. 이런 방식으로 문자열을 뒤집으면 O(n)의 시간 복잡도가 발생합니다. 여기서 n은 문자열의 길이입니다. 입력 읽기 및 문자열 비교와 같은 코드의 다른 작업은 상수 시간 작업이며 전체 시간 복잡성에 큰 영향을 미치지 않습니다.

공간 복잡도: 주어진 Java 코드의 공간 복잡도는 O(n)입니다. 여기서 n은 입력 문자열 str의 길이입니다. 이는 코드가 StringBuilder를 사용하여 입력 문자열의 역방향 복사본을 저장하고 StringBuilder에 필요한 공간이 입력 문자열의 길이에 비례하기 때문입니다.

참조

Palindrome에 대한 자세한 내용은 다음을 참조하십시오. 문자열 회문을 위한 프로그램 .