680.Valid Palindrome II

class Solution {
    public boolean validPalindrome(String s) {
        for (int i = 0; i < s.length() / 2; i++){
            if (s.charAt(i) != s.charAt(s.length() - i - 1)){
                int j = s.length() - i - 1;
                return isPalindrome(s, i, j - 1) || isPalindrome(s, i + 1, j);
            }
        }

        return true;
    }

    private boolean isPalindrome(String s, int i, int j){
        for (int k = 0; k <= (j - i) / 2; k++){
            if (s.charAt(i + k) != s.charAt(j - k)) return false;
        }
        return true;
    }
}

647 Palindromic Substrings

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

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

        for (int i = 0; i < n; i++){
            dp[i][i] = true;
        }

        for (int size = 1; size <= n; size++){
            for (int i = 0; i + size < n; i++){
                int j = i + size;
                if (s.charAt(i) != s.charAt(j)) continue;

                if (i + 1 == j || dp[i + 1][j - 1]){
                    dp[i][j] = true;
                    ans++;
                } 
                //System.out.println("i: " + i + " size: " + size + " ans: " + ans);
            }
        }

        return ans;
    }
}