2022.05.27 (lc_647_palindrome substring)

Method 1 ： Violent solution (O(n^3))

class Solution {
    public int countSubstrings(String s) {
        int n = s.length();
        int ans = 0;
        for (int i = 0; i < n; i++) {
            for (int j = i + 1; j <= n; j++) {
                if (satisfy(s.substring(i, j))) {
                    ans++;
                }
            }
        }
        return ans;
    }
    public boolean satisfy(String s) {
        int i = 0, j = s.length() - 1;
        while (i < j) {
            if (s.charAt(i) != s.charAt(j)) return false;
            i++;
            j--;
        }
        return true;
    }
}

  Method 2 ： Dynamic programming (O(n^2))

① Determine the state of ：dp[i][j] Express [i, j] Whether the string of is a palindrome substring ;

② Transfer equation ：if (s.charAt(i) == s.charAt(j) && (j - i <= 2 || dp[i + 1][j - 1])) {
                            dp[i][j] = true;
                        };

③ Initial conditions and boundary conditions ：dp[i][j] = false;

④ Computation order ： because dp[i][j] from dp[i + 1][j - 1] Introduction , So the outer layer for Cyclic reverse order , Inner layer for Cyclic positive order .

class Solution {
    public int countSubstrings(String s) {
        int n = s.length();
        //dp[i][j] Express [i,j] Whether the string of is a palindrome substring 
        boolean[][] dp = new boolean[n][n];
        int ans = 0;
        // Because of the demand dp[i][j] Need to know dp[i + 1][j - 1]
        // So the outer loop needs to be written backwards (i--), Inner loop needs to be written (j++)
        for (int i = n - 1; i >= 0; i--) {
            for (int j = i; j < n; j++) {
                // When s.charAt(i) != s.charAt(j) when ,dp[i][j] It must be false
                // When s.charAt(i) == s.charAt(j) And the number of elements is 1,2,3 or dp[i + 1][j - 1] by true when ,dp[i][j] It must be true
                if (s.charAt(i) == s.charAt(j) && (j - i <= 2 || dp[i + 1][j - 1])) {
                    dp[i][j] = true;
                    ans++;
                } 
            }
        }
        return ans;
    }
}

Method 3 ： Center expansion (O(n^2))

class Solution {
    public int countSubstrings(String s) {
        int n = s.length();
        int ans = 0;
        for (int i = 0; i < n; i++) {
            //j = 0, The palindrome center is a character 
            //j = 1, The palindrome center is two characters 
            for (int j = 0; j <= 1; j++) {
                int left = i;
                int right = i + j;
                while (left >= 0 && right < n && s.charAt(left) == s.charAt(right)) {
                    left--;
                    right++;
                    ans++;
                } 
            }
        }
        return ans;
    }
}