Java DP(rotate array): O(n^2) with O(n) space


  • 0
    K

    solution with O(n^2) space

    public int findLength(int[] A, int[] B) {
            int m = A.length, n = B.length;
            int [][]dp = new int[m+1][n+1];
            int len =0;
            for(int i=1;i<=m;++i){
                for(int j=1;j<=n;++j){
                    if(A[i-1]==B[j-1])
                        dp[i][j]=dp[i-1][j-1]+1;
                    if(len<dp[i][j])
                        len=dp[i][j];
                }
            }
            return len;
        }
    
    

    improved by rotate array

    public int findLength(int[] A, int[] B) {
             int m = A.length, n = B.length;
            int []dp = new int[n+1];
            int len =0;
            for(int i=1;i<=m;++i){
                int []clone = dp.clone();
                dp[0]=0;
                for(int j=1;j<=n;++j){
                    if(A[i-1]==B[j-1])
                        dp[j]=clone[j-1]+1;
                    else
                        dp[j]=0; //remember to assign to 0
                    if(len<dp[j])
                        len=dp[j];
                }
            }
            return len;
        }
    

Log in to reply
 

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