[C++] LeetCode : Longest Palindromic Substring

Question

Given a string s, return the longest palindromic substring in s.

문자열 s가 주어졌을 때, 가장 긴 palindromic 부분 문자열을 출력하라

 

제약사항

• 1 <= s.length <= 1000
• s 문자열은 오직 영문 문자열과 숫자로만 이루어져 있다. 

---

Solution

고려사항

• 문자열의 길이가 1 일때, ex) 'a'  
• palindromic substring이 없을 때, ex) 'abc'
• 문자열의 길이가 짝수/홀수 일 때 정상 동작 여부. ex) 'abba', 'aba'

---

Solution1 (Bruth Force)

가장 쉽게 생각할 수 있는 방법은 문자열의 문자를 시작점으로 palindromic을 만족하는 최대 문자열을 찾아,
그 길이를 갱신해주는 방식이다. 
이때 생각해볼 수 있는 시간복잡도는 O(s) * palindromic검사에 필요한 시간 복잡도로 palindromic검사를 최대 문자열의 길이부터 수행한다면 O(s^2)가 소요되고, 총 O(s^3)의 시간 복잡도가 소요된다.
문자열의 길이가 1000이기 때문에 1초정도 소요된다고 볼 수 있다. 

class Solution1 {
public:
	bool checkPalindrome(string check_str, int start, int end) {
		while (start < end) {
			if (check_str[start++] != check_str[end--]) {
				return false;
			}
		}

		return true;
	}
	string longestPalindrome(string s) {
		int n = s.length();
		int longest_length = 0;
		string longest_substring = "";

		for (int i = 0; i < n; i++) {
			if (n - i < longest_length) break;
			for (int j = n - 1; j >= i; j--) {
				if (j - i + 1 < longest_length) break;
				if (checkPalindrome(s, i, j)) {
					longest_substring = s.substr(i, j-i+1);
					longest_length = j - i + 1;
					break;
				}
			}
		}

		return longest_substring;
	}
};

• Time complexity : O(s³) 
• Space Complexity : O(1) 

Solution2

아래 예를 보자. 
"aabbccddccbbaa"

dd 는 palindrom이다. 
즉 dd가 palindrom 이라면 dd를 기준으로 ccddcc도 palindrom이다. 여기서 dd는 이미 palindrom이기 때문에 검사할 필요가 없다. 

즉, s의 i부터 j까지의 부분문자열을 S(i, j) 라 하고 P(i, j)를 palindrom을 만족 여부를 나타낸다고 가정할 때 아래와 같이 표현할 수 있다. 

 

여기서 확장한다면 P(i,j) = P(i+1, j-1) and S [i] == S [j]라고 표현할 수 있고 이를 적용하면 위 문제를 풀 수 있다.

base case

* P(i,i) = true

* P(i, i+1) = (S [i] == S [i+1])   

class Solution {
public:
	string longestPalindrome(string s) {
		int n = s.length();
		int longest_length = 0;
		string longest_substring = "";

		vector<vector<bool>> p(n, vector<bool>(n));
		for (int i = n-1; i >= 0; i--) {
			for (int j = i; j < n; j++) {
				if (i == j) { p[i][j] = true; }
				else if (s[i] == s[j]) {
					if (i == j - 1) p[i][j] = true;
					else {
						p[i][j] = p[i + 1][j - 1];
					}
				}

				if (p[i][j] && j - i + 1 > longest_length) {
					longest_length = j - i + 1;
					longest_substring = s.substr(i, j - i + 1);
				}
			}
		}

		return longest_substring;
	}
};

• Time complexity : O(n²) 
• Space Complexity : O(n²) 

출처 : https://leetcode.com/problems/longest-palindromic-substring/solution/

Longest Palindromic Substring - LeetCode