문자열을 뒤집은 후에도 그대로 유지되는 경우 문자열을 회문 문자열이라고 합니다.
이 특정 문제에서 우리는 길이가 같은 두 개의 문자열 'a'와 'b'를 제공했습니다. 일부 인덱스로 분할된 경우 작업은 문자열의 합이 회문을 만드는지 여부를 확인하는 것입니다.
길이가 '4'인 두 개의 문자열 'a'와 'b'가 있고 인덱스 '3'에서 두 문자열을 다음과 같이 분할한 후,
아아아 | ㄴ 및 bb |
aaa(첫 번째 문자열의 접두사) + a(두 번째 문자열의 접미사)는 회문이어야 합니다.
또는
b(첫 번째 문자열의 접미사) + bbb(두 번째 문자열의 접두사)는 회문이어야 합니다.
예를 들어
입력-1:
a = “abcdef”b = “fedcba”
출력:
True
설명: 인덱스 '2'에서 문자열 'a'와 문자열 'b'를 분할하면 다음과 같이 됩니다.
ABC | def와 먹이 | cba
abc(첫 번째 문자열의 접두사) + cba(두 번째 문자열의 접미사)는 회문 문자열을 만듭니다. 따라서 "True"를 반환합니다.
입력-2:
a = “eatable”b = “tableau”
출력:
False
설명: 이 두 문자열을 회문으로 만드는 방법은 없습니다.
이 문제를 해결하기 위한 접근 방식
이 특정 문제를 해결하기 위해 두 포인터 접근 방식을 사용합니다. 이 접근 방식에서는 먼저 낮은 값이 '0'을 가리키고 높은 값이 문자열의 마지막 문자를 가리키도록 두 개의 포인터(낮음 및 높음)를 초기화합니다.
두 문자열의 길이가 같으므로 2자 미만인 문자열이 있는지 확인합니다. 그렇다면 True를 반환합니다. 그렇지 않으면 포인터를 사용하여 전체 문자열을 반복하여 재귀적으로 검사합니다. 두 문자열이 같으면 True, 그렇지 않으면 False를 반환합니다.
- 각각 'a'와 'b'라는 두 개의 문자열을 사용합니다.
- 부울 함수 checkPalindromic(string a, string b)는 두 개의 문자열을 입력 매개변수로 사용하고 그에 따라 True 또는 False를 반환합니다.
- 낮음 =0 및 높음 =문자열 'b'의 길이로 두 개의 포인터(낮음 및 높음)를 초기화합니다.
- 문자열을 반복하고 두 문자열의 문자가 같은지 확인합니다.
- 부울 함수 split(string a, string b)는 두 개의 문자열을 가져와 회문이면 True를 반환하고 그렇지 않으면 False를 반환합니다.
예
#include <bits/stdc++.h>
using namespace std;
bool isPalindrome(string a, int low, int high) {
while (low < high) {
if (a[low] != a[high])
return false;
low++;
high--;
}
return true;
}
bool Split(string a, string b) {
int low = 0;
int high = b.size() - 1;
while (low < high and a[low] == b[high]) {
low++;
high--;
}
return isPalindrome(a, low, high) || isPalindrome(b, low, high);
}
bool checkPalindromic(string a, string b) {
if (a.size() < 2)
return true;
return Split(a, b) || Split(b, a);
}
int main() {
string a = "abcpqr";
string b = "mnocba";
if (checkPalindromic(a, b)) {
cout << "True" << endl;
} else {
cout << "False" << endl;
}
return 0;
} 위의 코드를 실행하면 다음과 같이 출력이 생성됩니다.
출력
True
설명: 인덱스 '2'에서 주어진 문자열 'abcpqr'과 'mnocba'를 다음과 같이 분할하면
a(접두사) =abc 및 b(접미사) =cba
a(접미사) =pqr 및 b(접두사) =mno
a(접두사) + b(접미사)가 회문을 만들어 출력이 True인 것을 관찰할 수 있습니다.