가장 긴 팰린드롬 문자열 구하기

팰린드롬이란 앞뒤가 똑같은 문자열인데 이번 문제는 하나의 문자열에서 가장 긴 팰린드롬을 구하는 문제이다.

 

2번째 문자부터 문자열의 길이가 홀수일 때, 짝수일 때의 인덱스 길이를 비교하여 가장 큰 길이를 구하고 string의 함수인 substr을 사용해서 문자열을 출력해준다. 

 

여기서 홀수일때와 짝수일 때라는 말은

vector<int> oddVector = getPalindorimDorim(str, index-1, index+1);
vector<int> evenVector = getPalindorimDorim(str, index-1, index);

 

팰린들롬을 구하는 부분 문자열의 길이를 짝수로 하나 홀수로 하나의 뜻이다. 예를 들어서 

 

abbbbsserasers

 

위와 같은 문자열이 있다면  2번째 문자열을 시작으로 ab, abb로 시작하는지 나누어 시작하는 것이다. 

 

그런 후 왼쪽의 인덱스와 오른쪽의 인덱스를 비교하며 가장 큰 길이를 구해준다. 

	while(leftIndex >= 0 && rightIndex < str.size()){
		if(str[leftIndex] != str[rightIndex])
			break;
		leftIndex--, rightIndex++;
	}

	return vector<int>{leftIndex+1, rightIndex};

그런 후 가장 큰 길이 인지 계속 체크해주며 마지막 값을 반환해주면 쉽게? 풀수 있다.

 

 

전체 코드

using namespace std;

vector<int> getPalindorimDorim(string str, int leftIndex, int rightIndex){

	while(leftIndex >= 0 && rightIndex < str.size()){
		if(str[leftIndex] != str[rightIndex])
			break;
		leftIndex--, rightIndex++;
	}

	return vector<int>{leftIndex+1, rightIndex};
}

string longestPalindromicSubstring(string str) {

	vector<int> currentVector{0, 1};
  	for(int index = 1; index < str.size(); index++){
  		vector<int> oddVector = getPalindorimDorim(str, index-1, index+1);
  		vector<int> evenVector = getPalindorimDorim(str, index-1, index);
		vector<int> longestVector = (oddVector[1] - oddVector[0]) > (evenVector[1] - evenVector[0])? oddVector:evenVector;		
		int currentVectorLength = currentVector[1]-currentVector[0];
		currentVector = (longestVector[1]-longestVector[0]) > currentVectorLength? longestVector : currentVector;
  	}
	
	return str.substr(currentVector[0], currentVector[1]-currentVector[0]);
}