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 Standard Longest Common Subsequence Problem: Answer is length of LCS
int commonChild(string s1, string s2) { int m = s1.length(); int n = s2.length(); vector<int> curr(n+1,0), prev(n+1,0); for(int i=1;i<=m;++i) { for(int j=1;j<=n;++j) { if(s1[i-1] == s2[j-1]) curr[j] = 1 + prev[j-1]; else curr[j] = max(curr[j-1],prev[j]); } prev = curr; } return curr[n]; }
+ 0 comments Python
I formed it as standard DP problem. Using fill-in-the-maxtrix to solve it. 1st of all, my solution below:def commonChild(s1, s2): arr = [[0 for _ in range(len(s1)+1)] for _ in range(len(s2)+1) ] for i in range(1,len(s1)+1,1): for j in range(1,len(s2)+1,1): arr[i][j]=max( ((arr[i-1][j-1] +1) if s1[i-1]==s2[j-1] else arr[i-1][j-1]), arr[i-1][j], arr[i][j-1] ) return arr[-1][-1]
+ 0 comments Typescript Solution
const commonChild = (s1: string, s2: string): number => { const m = s1.length; const n = s2.length; // @ts-ignore const matrix: number[][] = Array.from({length: m + 1}, () => Array(n + 1).fill(0)); let longestChild = matrix[0][0]; for (let i = 1; i <= m; i++) { for (let j = 1; j <= n; j++) { if (s1[i - 1] === s2[j - 1]) { matrix[i][j] = matrix[i - 1][j - 1] + 1; } else { matrix[i][j] = Math.max(matrix[i - 1][j], matrix[i][j - 1]); } if (matrix[i][j] > longestChild) { longestChild = matrix[i][j]; } } } return longestChild; }
+ 1 comment def commonChild(s1, s2): # Write your code here prev=[-1 for i in range(len(s2)+1)] for i in range(len(s1),-1,-1): curr=[-1 for i in range(len(s2)+1)] for j in range(len(s2),-1,-1): if i==len(s1) or j==len(s2): curr[j] = 0 else: if s1[i]==s2[j]: curr[j] = 1+prev[j+1] else: curr[j] = max(prev[j],curr[j+1]) prev=curr return curr[0]
+ 0 comments longest common subsquence with tabulation
Load more conversations
Sort 649 Discussions, By:
Please Login in order to post a comment