LeetCode 5번 Longest Palindromic Substring

---

문제 링크

Longest Palindromic Substring - LeetCode

---

문제

Example 1:

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

Example 2:

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

Example 3:

Input: s = "a"
Output: "a"

Example 4:

Input: s = "ac"
Output: "a"

---

풀이

이 문제는 주어진 문자열에서 가장 긴 팰린드롭을 구하면 되는 문제입니다.

class Solution {
private:

	string answer;
public:
	void Palindrome(int _left, int _right, string& _s)
	{
		//cout << _left << " " << _right << endl;
		while (true)
		{
			if (_left < 0 || _right >= _s.size())
			{
				break;
			}
			else if (_s[_left] != _s[_right])
			{
				break;
			}
			else
			{
				--_left;
				++_right;
			}
		}
		
		int len = _right - _left - 1;

		if (answer.size() < len)
		{
			answer = _s.substr(_left + 1, len);
		}
	}

	string longestPalindrome(string s)
	{
		for (int i = 0; i < s.size(); i++)
		{
			Palindrome(i - 1, i + 1, s);
			Palindrome(i, i + 1, s);	// abba 같은 경우
		}
		return answer;
	}
};

Time Submitted	Status	RunTime	Memory
07/25/2021 22:22	Accepted	28 ms	14.4 MB

시간 복잡도 : O(N^2)