LCS , C++ concise primary and optimized O(n) space solution


  • 0
    H

    ①dp[i][j] represents the largest common substring between vector v1 ends with i index and v2 end with j index.
    ②In c++, former answer will get memory exceed limit,but we find that dp[i][j] has relation only with last dp[i-1][j-1],so we can use dp[j] to represent last row dp and use now[j] to represent current row answer.
    Hope it can give you some help.

    int findLength(vector<int>& A, vector<int>& B) {
            int m=A.size(),n=B.size();
            vector<vector<int>> dp(m+1,vector<int>(n+1,0));int r=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,r=max(r,dp[i][j]);
                }
            }
            return r;
        }
    
    int findLength(vector<int>& A, vector<int>& B) {
            int m=A.size(),n=B.size();
            vector<int> dp(n+1,0);int r=0;
            for(int i=1;i<=m;i++){
                vector<int> now(n+1,0);
                for(int j=1;j<=n;j++){
                    if(A[i-1]==B[j-1])now[j]=dp[j-1]+1,r=max(r,now[j]);
                }
                dp=now;
            }
            return r;
        }
    

Log in to reply
 

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