647. Palindromic Substrings

Problem

Palindromic Substrings

Approach

• the easiest way is to check every substring of the given string
• use the DP. DP[i][j] means the substring, which is from i to j, is palindromic only when DP[i - 1][j - 1] is palindromic and str.charAt(i) is same as str.charAt(j).

Code

1. for approach 1

   class Solution {
    public boolean isPalin(String s){
        int i = 0;
        int j = s.length() - 1;
        while(i <= j){
            if(s.charAt(i) != s.charAt(j)){
                return false;
            }
            i ++;
            j --;
        }
        return true;
    }
    public int countSubstrings(String s) {
        Set<String> exist = new HashSet<>();
        int ans = 0;
        for(int i = 0; i < s.length(); i ++){
            for(int j = i; j < s.length(); j ++){
                String subs = s.substring(i, j + 1);
                if(exist.contains(subs)){
                    ans ++;
                }
                else if(isPalin(subs)){
                    exist.add(subs);
                    ans ++;
                }
            }
        }
        return ans;
    }
   }
   

2. for approach 2

   class Solution {
    public int countSubstrings(String s) {
        int ans = 0;
        int N = s.length();
        boolean[][] dp = new boolean[N][N];
        // for len = 1 of substring from i to i
        for(int i = 0; i < N; i ++){
            dp[i][i] = true;
            ans ++;
        }
        // for len = 2 of substring from i to i + 1
        for(int i = 0; i < N - 1; i ++){
            if(s.charAt(i) == s.charAt(i + 1)){
                dp[i][i + 1] = true;
                ans ++;
            }
            else{
                dp[i][i + 1] = false;
            }
        }
        // for len >= 3
        for(int len = 3; len <= N; len ++){
            for(int i = 0; i < N; i ++){
                int j = i + len - 1;
                if(i + 1 < N && j >= 1 && j < N && s.charAt(i) == s.charAt(j) && dp[i + 1][j - 1]){
                    dp[i][j] = true;
                    ans ++;
                }
            }
        }
        return ans;
    }
   }