이 문제에서 문자열 str, 각각 substring[L...R]에 대한 두 값 L과 R로 구성된 쿼리의 Q 수를 받습니다. 우리의 임무는 하위 문자열[L…R]이 회문인지 여부를 확인하기 위해 쿼리를 해결하는 프로그램을 만드는 것입니다.
문제 설명 − 각 질의를 풀기 위해서는 L~R 범위 내에서 생성된 부분 문자열이 회문인지 아닌지를 확인해야 한다.
문제를 이해하기 위해 예를 들어보겠습니다.
입력
str = “abccbeba” , Q = 3 Query[][] = {{1, 4}, {0, 6}, {4, 6}}
출력
Palindrome Not Palindrome Palindrome
설명
Creating all substring for the given substrings : Substring[1...4] = “bccb”, it is a palindrome Substring[0...6] = “abccbeb”, it is a not palindrome Substring[4...6] = “beb”, it is a palindrome
해결 방법
문제에 대한 간단한 해결책은 각 쿼리를 해결하는 것입니다. 이를 해결하려면 인덱스 범위 L에서 R까지의 하위 문자열을 찾아야 합니다. 그리고 하위 문자열이 회문인지 확인합니다.
우리 솔루션의 작동을 설명하는 프로그램
예
#include <bits/stdc++.h> using namespace std; int isPallindrome(string str){ int i, length; int flag = 0; length = str.length(); for(i=0;i < length ;i++){ if(str[i] != str[length-i-1]) { flag = 1; break; } } if (flag==1) return 1; return 0; } void solveAllQueries(string str, int Q, int query[][2]){ for(int i = 0; i < Q; i++){ isPallindrome(str.substr(query[i][0] - 1, query[i][1] - 1))?cout<<"Palindrome\n":cout<<"Not palindrome!\n"; } } int main() { string str = "abccbeba"; int Q = 3; int query[Q][2] = {{1, 3}, {2, 5}, {4, 5}}; solveAllQueries(str, Q, query); return 0; }
출력
Palindrome Not palindrome! Palindrome
이것은 순진한 접근 방식이지만 효율적인 접근 방식은 아닙니다.
문제에 대한 효율적인 솔루션은 동적 프로그래밍 접근 방식을 사용하는 것입니다. 해결을 위해 부분 문자열[i...j]이 DP[i][j]에 대한 회문인지 여부를 나타내는 부울 값을 저장하는 2차원 배열인 DP 배열을 만들어야 합니다.
이 DP 행렬을 만들고 각 쿼리의 모든 L-R 값을 확인합니다.
우리 솔루션의 작동을 설명하는 프로그램
예
#include <bits/stdc++.h> using namespace std; void computeDP(int DP[][50], string str){ int length = str.size(); int i, j; for (i = 0; i < length; i++) { for (j = 0; j < length; j++) DP[i][j] = 0; } for (j = 1; j <= length; j++) { for (i = 0; i <= length - j; i++) { if (j <= 2) { if (str[i] == str[i + j - 1]) DP[i][i + j - 1] = 1; } else if (str[i] == str[i + j - 1]) DP[i][i + j - 1] = DP[i + 1][i + j - 2]; } } } void solveAllQueries(string str, int Q, int query[][2]){ int DP[50][50]; computeDP(DP, str); for(int i = 0; i < Q; i++){ DP[query[i][0] - 1][query[i][1] - 1]?cout<<"not palindrome!\n":cout<<"palindrome!\n"; } } int main() { string str = "abccbeba"; int Q = 3; int query[Q][2] = {{1, 3}, {2, 5}, {4, 5}}; solveAllQueries(str, Q, query); return 0; }
출력
palindrome! not palindrome! palindrome!