Java DP solution based on longest palindromic substring


  • 12

    This solution is almost same as the DP solution for longest palindromic substring, instead of storing the longest, just get the count of palindromic substrings.

    public int countSubstrings(String s) {
        int n = s.length();
        int res = 0;
        boolean[][] dp = new boolean[n][n];
        for (int i = n - 1; i >= 0; i--) {
            for (int j = i; j < n; j++) {
                dp[i][j] = s.charAt(i) == s.charAt(j) && (j - i < 3 || dp[i + 1][j - 1]);
                if(dp[i][j]) ++res;
            }
        }
        return res;
    }
    
    

  • 1
    J

    @johnyrufus16 How about adding the meaning of the 3 which appears in line 7?
    It is for the one or two characters, like "a", "aa". Because that string cannot have dp[i + 1][j - 1] value.

    Anyway, thank you for your nice code! I can understand the solution using DP!


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.