[LeetCode, 리트코드] Longest Palindromic Substring

1. Problem

Given a string s, find the longest palindromic substring in s. You may assume that the maximum length of s is 1000.

주어진 문자열 s에 대해 부분문자열 중 가장 긴 펠린드롬을 구하라. 문자열의 길이는 1000으로 가정하라

2. Solution

동적계획법을 이용하면 어렵지 않게 풀 수 있다. 동적계획법의 이산수학식은 다음과 같다

$P(i,j)=\{\begin{array}{ll}\text{true,}& \text{if the substring }{S}_i\dots S_j\text{ is a palindrome}\\ \text{false,}& \text{otherwise.}\end{array}$

$P(i, j) = ( P(i+1, j-1) \text{ and } S_i == S_j )$

$P(i, i) = true$

$P(i, i+1) = ( S_i == S_{i+1} )$

3. What I solved

class Solution {
    int left;
    int right;
    bool cache[1001][1001];
public:
    string longestPalindrome(string s) {
        if(s.size() <= 1) 
            return s;
        
        memset(cache, false, sizeof(cache));
        
        for(int i=0; i= s.size())    
            return;
        
        if(i == j || (i + 1 == j && s[i] == s[j]) ||
           (i + 1 < s.size() && j - 1 >= 0 && cache[i+1][j-1] && s[i] == s[j])){
            cache[i][j] = true;
            if(j - i > right - left){
                left = i;
                right = j;
            }
            checkPalindrom(s, i-1, j+1);
        }
    }
};

4. Best Solution

Same as above

위와 동일