dp solution beats 100%


  • 0
    L

    public class Solution {
    public int countSubstrings(String s) {
    if(s == null || s.length() <= 0)
    return 0;

        int len = s.length();
        int[][] dp = new int[len][len];
    
        //init
        for(int i = 0; i < len; i++)
        	dp[i][i] = 1;
    
        //start dp
        for(int j = 0; j < len; j++) {
        	for(int i = j - 1; i >= 0; i--) {
    
        		dp[i][j] = dp[i][j-1] + dp[i+1][j] - dp[i+1][j-1];
        		if(isPalindrome(s, i, j))
        			dp[i][j] += 1;
        	}
        }
        return dp[0][len-1];
    }
    
    public boolean isPalindrome(String s, int i, int j) {
    	while(i <= j) {
    		if(s.charAt(i) != s.charAt(j))
    			return false;
    		i++;
    		j--;
    	}
    	return true;
    }
    

    }


Log in to reply
 

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