[LeetCode]가장 긴 팰린드롬 부분 문자열

문제

가장 긴 팰린드롬 부분 문자열을 출력하라

• Example 1:

Input: s = "babad"
Output: "bab"
Explanation: "aba" is also a valid answer.

• Example 2:

Input: s = "cbbd"
Output: "bb"

코드

class Solution {
public:
    string longestPalindrome(string s) {

    string a;
	string S_reverse;
	
	int num = 1;
	
	int size = s.size();
	bool isAnswer = false;
	
	while (!isAnswer)
	{
		for (int i = 0; i < num; i++)
		{
			a = s.substr(i, size);

			S_reverse = a;
			reverse(S_reverse.begin(), S_reverse.end());

			if (a.compare(S_reverse) == 0)
			{
				isAnswer = true;
				return a;
			}
		}
       
		a.clear();
		S_reverse.clear();
		num++;
		size--;
	}
    return a;
	}
};

풀이

• string의 substr을 이용하여 문제를 해석하였다.
• 먼저 최대길이의 문자를 확인하면서 점차 길이를 줄여 나간다.
• 해당 문자가 팰린드롬인게 확인될경우 즉시 return하기 때문에 가장 긴 값이 출력될 것이다.

결과

Time Limit Exceeded... 수정 예정

---

https://leetcode.com/problems/longest-palindromic-substring/