25 ms Java DP. Space - O(n^2)


  • 1
    D

    Here is a DP solution. dp[i][j] is true is the substring from index i to index j is a palindrome. Each time I encounter a palindrome, I increment the count.
    dp[i][j] will depend upon the the ith character matching the jth character and whether the substring from i+1 to j-1 is a palindrome or not.

    '''
    public class Solution {
    public int countSubstrings(String s) {

        int len = s.length();
        boolean[][] dp = new boolean[len][len];
        int count = 0;
        
        for(int i = 0; i < len; i++)
            Arrays.fill(dp[i], true);
        
        for(int i = len - 1; i >= 0; i--){
            for(int j = i; j < len; j++){
                if(i == j){
                    count++;
                    continue;
                }
                
                dp[i][j] = (s.charAt(i) == s.charAt(j)) && dp[i+1][j-1];
                if(dp[i][j])
                    count++;
            }
        }
        
        return count;
    }
    

    }
    '''


Log in to reply
 

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