647. Palindromic Substrings

Link

Solution

Palindromic 問題優先考慮DP, 因為可以透過延展來取得下一階段的答案

dp[i][j] to present if s[i] ... s[j] can be plindromic or not.

  public int countSubstrings(String s) {
        
        char[] s1 = s.toCharArray();
        int n = s1.length;
        boolean[][] dp = new boolean[n][n];
        int count = 0;    
        for(int i = 0; i < n; i++){
            dp[i][i] = true;
            count++;
        }
            
        for(int dist = 1; dist < n; dist++){
            for(int i = 0; i + dist < n; i++){
                int j = dist + i;
                if(s1[i] == s1[j]){
                    if(dist == 1)
                    {
                        dp[i][j] = true;
                    }
                    else
                        dp[i][j] = dp[i+1][j-1];
                }
                else{
                    dp[i][j] = false;
                }
                if(dp[i][j]) count++;
            }
        }
        return count;
    }