(String, Medium) Palindromic Substrings

https://leetcode.com/problems/palindromic-substrings/description/

이전 문제를 참고해서 "팰린드롬의 중심 확장" 개념을 익혔다.
그것을 기반으로 해서 똑같이 odd기준, even기준으로 최대 확장될 수 있는 팰린드롬 카운트를 세서 계속 누적하면 정답이 나올 것 같았고, 실제로 그랬다.

class Solution {
    public int countSubstrings(String s) {
        int count = 0;
        for (int i=0; i<s.length(); i++) {
            int odd = countPalindrom(s, i, i);
            int even = countPalindrom(s, i, i + 1);

            count += odd + even;
        }
        return count;
    }

    private int countPalindrom(String s, int left, int right) {
        int n = s.length();
        int count = 0;
        while (left >= 0 && right < n && s.charAt(left) == s.charAt(right)) {
            left--;
            right++;
            count++;
        }
        return count;
    }
}

다른 풀이를 참고해보면 DP 기반 풀이도 있다고 한다.
2차원 dp배열을 통해 dp[i][j] = s[i..j]가 팰린드롬인가를 저장한다.

길이 1인 것들은 모두 팰린드롬이므로 dp[i][i]는 모두 true로 세팅하며 카운트해주고,
이후에 길이 2 이상에서 i로 +1해가면서 아래 조건 중 하나가 참이면 팰린드롬 확장이 가능하다고 판단한다.

• i와 j가 같은데, 길이가 2임 --> 뒤집을 수 있음
• i와 j가 같은데, dp[i + 1][j - 1]이 참임 --> 더 안쪽이 이미 팰린드롬이면 i와 j포함해도 팰린드롬임

class Solution {
    public int countSubstrings(String s) {
        int n = s.length();
        boolean[][] dp = new boolean[n][n];
        int count = 0;

        // 길이 1
        for (int i = 0; i < n; i++) {
            dp[i][i] = true;
            count++;
        }

        // 길이 2 이상
        for (int len = 2; len <= n; len++) {
            for (int i = 0; i + len - 1 < n; i++) {
                int j = i + len - 1;
                if (s.charAt(i) == s.charAt(j)) {
                    if (len == 2 || dp[i + 1][j - 1]) {
                        dp[i][j] = true;
                        count++;
                    }
                }
            }
        }
        return count;
    }
}