[LeetCode] 5. Longest Palindromic Substring (C++)

문제

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

Longest Palindromic Substring - LeetCode

 

 

풀이

 

난이도: Medium 

 

다이나믹 프로그래밍으로 해결 가능한 유명한 문제.

 

dp[start][end] 는 문자열의 start에서 end 까지의 최대 팰린드롬 길이를 의미한다.

팰린드롬이 되려면 일단, start와 end의 문자가 같아야한다.

 

따라서 start와 end의 문자가 같은 경우만 팰린드롬 여부를 확인하면 된다.

여기서 dp에는 가장 긴 팰린드롬 길이가 저장되어 있으므로,

dp[start][end] = dp[start +1][end -1] + 2가 된다.

 

이러한 알고리즘은  start와 end 모두 확인해야 하므로 O(N^2)의 시간 복잡도와 공간 복잡도가 소요된다.

 

 

 

다이나믹으로 해결하는 것은 너무 많이 봐왔으니 다른 해결법도 확인해보자.

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

 

해결법의 Approach 4: Expand Around Center 를 확인해보자.

 

팰린드롬은 가운데의 문자를 기준으로 대칭이다.

가운대 문자는 단 한개 ex) "aba" 에서의 "b", "abbba" 에서의 "b"

혹은 두개가 될 수 있다. ex) "abba" 에서의  "bb", "abbbba"에서의 "bb"

 

따라서 문자열을 순서대로 순회하면서 두가지 경우에서, 펠린드롬 여부를 확인하면서 양쪽으로 확장해 나간다.

이러한 알고리즘은  O(N^2)의 시간 복잡도가 소모되지만, 공간 복잡도는 O(1)이다.

 

단, 다이나믹은 이미 계산한 값을 바로 이용하므로 공간 복잡도는 높더라도 좀더 빠를 수도 있다고 생각한다.

 

 

코드

 

	class Solution {
	private:
	int dp[1000][1000];
	public:
	string longestPalindrome(string s) {
	memset(dp, 0, sizeof(dp));
	string answer = s.substr(0,1);
	for (int start = s.length()-1; start>=0 ; --start ) {
	dp[start][start] = 1;
	for (int end = start +1; end <s.length(); ++end) {
	if (s[start] == s[end]) {
	if (start == (end - 1)) {
	dp[start][end] = 2;
	if (answer.length() < (end - start + 1))
	answer = s.substr(start, 2);
	}else if (dp[start + 1][end - 1] != 0) {
	dp[start][end] = dp[start + 1][end - 1] + 2;
	if (answer.length() < (end - start + 1))
	answer = s.substr(start, end - start + 1);
	}
	}
	}
	}
	return answer;
	}
	};

view raw 5. Longest Palindromic Substring.cpp hosted with ❤ by GitHub