// 动态规划法

public int countSubstrings(String s) {

int n = s.length();

int[][] dp = new int[n][n];

for (int i = 0; i < n; i++) {

dp[i][i] = 1;

}

// 只需要半个矩阵即可

for (int i = n - 1; i >= 0; i--) {

for (int j = i + 1; j < n; j++) {

if (j == i + 1) {

dp[i][j] = s.charAt(i) == s.charAt(j) ? 1 : 0;

continue;

}

dp[i][j] = (dp[i+1][j-1] == 1 && s.charAt(i) == s.charAt(j)) ? 1 : 0;

}

}

int count = 0;

for (int i = 0; i < n; i++) {

for (int j = i; j < n; j++) {

count += dp[i][j];

}

}

return count;

}

// 分治法

public int countSubstrings1(String s) {

int count = 0;

for (int i = 0; i < s.length(); i++) {

count += countSubStrings(s, i, i);

count += countSubStrings(s, i, i+1);

}

return count;

}

private int countSubStrings(String s, int start, int end) {

int count = 0;

while (start >= 0 && end < s.length() && s.charAt(start) == s.charAt(end)) {

count++;

start--;

end++;

}

return count;

}