DP Solution


  • 0
    Y
    public int countSubstrings(String s) {
    	if (s == null || s.length() == 0) {
    		return 0;
    	}
    	int n = s.length();
    	int count = 0;
    	boolean[][] result = new boolean[n][n];
    	for (int i = 0; i < n; i++) {
    		for (int j = 0; j < n - i; j++) {
    			if (s.charAt(i + j) == s.charAt(j)) {
    				result[j][i + j] = j + 1 >= i + j - 1 || result[j + 1][i + j - 1] ? true : false; 
    			}
    			if (result[j][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.