leetCode - Longest Palindromic Substring(DP)

문제

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

 

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"

 

Constraints:

• 1 <= s.length <= 1000
• s consist of only digits and English letters (lower-case and/or upper-case),

 

---

풀이방법

• 테이블 : n까지의 가장 긴 회문 문자열을 찾자
  • 문자열 하나 ex)a, b, c,
  • 문자열 두개 ex) aa, bb, cc
  • 문자열 세개 이상 ex) aba, aca, bccb, fcdcf
• 점화식 : dp(n) = max(문자열하나.length, 문자열두개.length, 문자열세개이상.length);
• 초기값: dp를 이중 배열로 만들고 false로 초기화

 

const longestPalindrome = function (s) {
    if (s.length <= 1) return s;

    // 처음에는 왜 중첩배열로 만드는 지 이해가 안감.
    // 나름 생각한게 재방문을 하지 않게 하기위해서 중첩배열을 만듦
    const dp = Array.from(new Array(s.length), () => (new Array(s.length).fill(false)));

    let lps = '';

    //문자열하나
    for (let i = 0; i < s.length; i++) {
        dp[i][i] = true;
        lps = s[i];
    }

    // 문자열 두개
    for (let i = 0; i < s.length; i++) {
        if (s[i] === s[i + 1]) dp[i][i + 1] = true;
        if (dp[i][i + 1]) lps = s.substring(i, i + 2);
    }
   
    // 문자열 세개
    //바깥 반복문을 돌 때 문자열 길이부터 i>=0까지 차례로 감소하는 로직을 구현했는데,
    //왜 이렇게 했는지 처음에는 이해가 안감. 생각해보니 나름 결론을 내렸는데, 만약 
    //아래서부터 즉, i=0부터 시작해서 문자열 길이까지 반복을 돌면 반복문 안에 있는
    //dp[i+1][j-1]이 참인지 판단을 할 수 없음. 하지만 위에서부터 반복문을 돌면
    //밑에서 부터 dp를 쌓아가니깐 판별할 수 있음.... 
    // 이렇게 생각을 했는데, 사실 맞는 건지 잘모르겠음.
    for (let i = s.length - 1; i >= 0; i--) {
        for (let j = i + 2; j < s.length; j++) {
            dp[i][j] = dp[i + 1][j - 1] && s[i] === s[j];
            if (dp[i][j]) lps = lps.length < (j - i + 1) ? s.substring(i, j + 1) : lps;
        }
    }

    return lps;
};