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.
- Prepare
- Algorithms
- Strings
- Common Child
- Discussions
Common Child
Common Child
+ 0 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.
int commonChild(string s1, string s2) { /* 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. */ const auto N = 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 0 auto IdxI = [](int i){ return (i+2)%2; }; auto IdxJ = [N](int j){ return (j+(N+1))%(N+1); }; bool ismatch = false; for (signed i=0; i<N; ++i) { for (signed j=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)] }); } } return dp[IdxI(N-1)][IdxJ(N-1)]; }
+ 0 comments DP in C++ code, simple version
int max_substr(const std::string& s1, const std::string& s2, int pos1, int pos2, std::vector<std::vector<int>>& mem) { if (pos1 == s1.size() || pos2 == s2.size()) { return 0; } if (mem[pos1][pos2] != -1) { return mem[pos1][pos2]; } if (s1[pos1] == s2[pos2]) { mem[pos1][pos2] = 1 + max_substr(s1, s2, pos1 + 1, pos2 + 1, mem); return mem[pos1][pos2]; } mem[pos1][pos2] = std::max(max_substr(s1, s2, pos1, pos2 + 1, mem), max_substr(s1, s2, pos1 + 1, pos2, mem)); return mem[pos1][pos2]; } int commonChild(string s1, string s2) { std::vector<std::vector<int>> mem(s1.size(), std::vector<int>(s2.size(), -1)); return max_substr(s1, s2, 0, 0, mem); }
+ 0 comments public static int commonChild(string s1, string s2) { int m = s1.Length + 1, n = s2.Length + 1; int[,] LCS = new int[m, n]; for (int i = 1; i < m; i++) { for (int j = 1; j < n; j++) { if (s1[i - 1] == s2[j - 1]) LCS[i, j] = LCS[(i - 1), (j - 1)] + 1; else LCS[i, j] = Math.Max(LCS[(i - 1), j], LCS[i, (j - 1)]); } } return LCS[(m - 1), (n - 1)]; }
+ 1 comment I quite liked this Python, but it turned out too slow:
from collections import Counter def commonChild(s1, s2): ctable = Counter() for i in range(len(s1)): for j in range(len(s2)): if s1[i] == s2[j]: ctable[(i, j)] = 1 + ctable[(i-1, j-1)] else: a, b = ctable[(i, j-1)], ctable[(i-1, j)] if a or b: ctable[(i, j)] = max(a, b) values = list(ctable.values()) return values[-1] if values else 0
+ 0 comments A C++ version:
int commonChild(const std::string &s1, const std::string &s2) { std::vector<int> vtable[2]; size_t s1_len = s1.length() + 1; size_t s2_len = s2.length() + 1; vtable[0].resize(s2_len, 0); vtable[1] = vtable[0]; for (auto i = 1; i < s1_len; ++i) { auto &prev = vtable[(i+1)%2]; auto &curr = vtable[i%2]; for (auto j = 1; j < s2_len; ++j) { if (s1[i-1] == s2[j-1]) { curr[j] = prev[j-1] + 1; } else { if (prev[j] > curr[j-1]) curr[j] = prev[j]; else curr[j] = curr[j-1]; } } } return vtable[(s1_len+1)%2][s2_len-1]; }
Load more conversations
Sort 630 Discussions, By:
Please Login in order to post a comment