Palindromic Substrings

就是把判断的那个dp矩阵拿出来之后一个个数就行了

class Solution(object):
    def countSubstrings(self, s):
        """
        :type s: str
        :rtype: int
        """
        n = len(s)
        dp = [[False] * n for _ in xrange(n)]

        for i in xrange(n):
            for j in xrange(i, -1, -1):
                if j == i:
                    dp[j][i] = True
                elif j + 1 == i:
                    dp[j][i] = (s[j] == s[i])
                else:
                    dp[j][i] = (s[j] == s[i] and dp[j + 1][i - 1])

        result = 0
        for i in xrange(n):
            for j in xrange(i, n):
                if dp[i][j]:
                    result += 1

        return result

Java版本

class Solution {
    public String longestPalindrome(String s) {
        int n = s.length();
        char[] sArray = s.toCharArray();
        boolean[][] dp = new boolean[n][n];
        int distance = 0;
        int start = -1;
        int end = -1;

        for (int i = 0; i < n; i++) {
            for (int j = i; j >= 0; j--) {
                if (j == i) {
                    dp[j][i] = true;
                } else if (j + 1 == i) {
                    dp[j][i] = (sArray[j] == sArray[i]);
                } else if (sArray[j] == sArray[i]) {
                    dp[j][i] = dp[j + 1][i - 1];
                } else {
                    dp[j][i] = false;
                }

                if (i - j + 1 > distance && dp[j][i] == true) {
                    distance = i - j + 1;
                    start = j;
                    end = i;
                }
            }
        }

        return s.substring(start, end + 1);
    }
}