simple O(N^2) time O(N) space DP solution


  • 0
    J

    NxN space solution is self explained as below. we could safely reduce space to 2*n by using two rows to mimic all imaginary rows in 2d solution. the trick is to mod the rowIndex.

    /**
        s(i,j) is a palindrome, only when s(i-1,j+1) is a palindrome and s[i]==s[j]. special cases include, i=j and i=j+1
        **/
        public int countSubstrings2D(String s) {
            if(s==null||s.length()==0) return 0;
            int n=s.length();
            boolean[][] dp=new boolean[n][n];
            int countOfTrues=0;
            for(int i=n-1;i>=0;i--){
                for(int j=i;j<n;j++){
                    dp[i][j]=(s.charAt(i)==s.charAt(j))&&(j<i+2||dp[i+1][j-1]);
                    if(dp[i][j]) countOfTrues++;
                }
            }
            return countOfTrues;
        }
        /*
        reduce to 1-D space
        */
        public int countSubstrings1D(String s) {
            if(s==null||s.length()==0) return 0;
            int n=s.length();
            boolean[][] dp=new boolean[2][n];
            int countOfTrues=0;
            for(int i=n-1;i>=0;i--){
                for(int j=i;j<n;j++){
                    // use 2 rows to swap to save spaces
                    int curRow=i%2;
                    int preRow=(i+1)%2;
                    dp[curRow][j]=(s.charAt(i)==s.charAt(j))&&(j<i+2||dp[preRow][j-1]);
                    if(dp[curRow][j]) countOfTrues++;
                }
            }
            return countOfTrues;
        }
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.