We use cookies to ensure you have the best browsing experience on our website. Please read our cookie policy for more information about how we use cookies.
here is a solution with time complexity = O(N^2) and space complexity = O(2*N) = O(N). It passes all test cases
see comments in the code for explanation.
intcommonChild(strings1,strings2){/* denote dp[i][j] is the length of longest child between s1[0...i] and s2[0...j] consider sub-problems of dp[i][j]. bool ismatch = s1[i] == s2[j]; dp[i][j] = max(dp[i-1][j-1]+ismatch, // both s1[i],s2[j] are skipped or matched dp[i-1][j], // skip s1[i] dp[i][j-1]) // skip s2[j] initially, dp[-1][-1] = 0 dp[-1][0] = 0 dp[0][-1] = 0 update dp by dp[0][0] -> dp[0][1] -> dp[0][2] -> ... -> dp[0][N-1] -> dp[1][0] -> dp[1][1] -> dp[1][2] -> ... -> dp[1][N-1] -> ... dp[N-1][N-1] and the final result is dp[N-1][N-1] the actual storage for dp[][] can be reduced to dp[0..1][0...N-1] when we iterate i at outter loop, and j at inner loop. */constautoN=s1.size();assert(s2.size()==N);vector<vector<int>>dp(2,vector<int>(N+1,0));// N+1 is for the dp[i][-1] which is always 0autoIdxI=[](inti){return(i+2)%2;};autoIdxJ=[N](intj){return(j+(N+1))%(N+1);};boolismatch=false;for(signedi=0;i<N;++i){for(signedj=0;j<N;++j){ismatch=s1[i]==s2[j];dp[IdxI(i)][IdxJ(j)]=max({dp[IdxI(i-1)][IdxJ(j-1)]+ismatch,dp[IdxI(i)][IdxJ(j-1)],dp[IdxI(i-1)][IdxJ(j)]});}}returndp[IdxI(N-1)][IdxJ(N-1)];}
Common Child
You are viewing a single comment's thread. Return to all comments →
here is a solution with time complexity = O(N^2) and space complexity = O(2*N) = O(N). It passes all test cases
see comments in the code for explanation.