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.
  1. Prepare
  2. Algorithms
  3. Strings
  4. Common Child
  5. Discussions

Common Child

Sort by

recency

|

665 Discussions

|

  • AbdelrhmanAdawy
     + 0 comments

    C language solution using dynamic programming (recursion with memory)

    int max(int a , int b)
{
    return ((a >= b)?(a):(b));
}

int LSC(char* s1, char* s2 , int len_1  , int len_2 , int i , int j , int ** Hash_Table)
{
    if(i>=len_1 || j>= len_2)
    {
        return 0;
    }
    else if ( Hash_Table[i][j] != 0 ) {
        return Hash_Table[i][j];
    }
    else if(s1[i] == s2[j])
    {
        //rewrite that code to store the value
        int val = 1+LSC(s1 , s2 ,len_1 ,len_2 , i+1 , j+1 , Hash_Table);
        Hash_Table[i][j] = val;
        return val;
    }
    else {
        int val = max(LSC(s1 , s2 , len_1 , len_2  , i+1 , j , Hash_Table) , LSC(s1 , s2 , len_1 , len_2 , i , j+1 , Hash_Table));
        Hash_Table[i][j] = val;
        return val;  
        }
}


/*
 * Complete the 'commonChild' function below.
 *
 * The function is expected to return an INTEGER.
 * The function accepts following parameters:
 *  1. STRING s1
 *  2. STRING s2
 */

int commonChild(char* s1, char* s2) {
    int len_1 = strlen(s1) , len_2 = strlen(s2);
    
    int ** Hash_Table = calloc(len_1, sizeof(int*));
    for (int i = 0; i<len_1 ; i++) {
        Hash_Table[i] = calloc(len_2, sizeof(int));
    }
        
    return LSC(s1, s2 ,len_1 , len_2 , 0 , 0 , Hash_Table);
}

  • dellvecchio
     + 0 comments

    ` def commonChild(s1, s2): # Write your code here matrix = [[0 for j in range(len(s2))] for i in range(len(s1))]

    if s1[0] == s2[0]:
    matrix[0][0] = 1
else:
    matrix[0][0] = 0
for j in range(1, len(s2)):
    if s1[0] == s2[j]:
        matrix[0][j] = 1
    else:
        matrix[0][j] = matrix[0][j-1]
for i in range(1, len(s1)):
    if s2[0] == s1[i]:
        matrix[i][0] = 1
    else:
        matrix[i][0] = matrix[i-1][0]

for i in range(1, len(s1)):
    for j in range(1, len(s2)):
        if s1[i] == s2[j]:
            matrix[i][j] = 1 + matrix[i-1][j-1]
        else:
            matrix[i][j] = max(matrix[i][j-1], matrix[i-1][j])

return matrix[len(s1)-1][len(s2)-1]

  • shreyavishwalin1
     + 0 comments

    My Solution in Python 3

    def commonChild(s1, s2):
    n = len(s1)
    m = len(s2)
    
    # Initialize dp array
    dp = [[0] * (m + 1) for _ in range(n + 1)]
    
    # Build dp array
    for i in range(1, n + 1):
        for j in range(1, m + 1):
            if s1[i - 1] == s2[j - 1]:
                dp[i][j] = dp[i - 1][j - 1] + 1
            else:
                dp[i][j] = max(dp[i - 1][j], dp[i][j - 1])
    
    # The length of the longest common child
    return dp[n][m]

  • IGomes
     + 0 comments

    https://www.geeksforgeeks.org/longest-common-subsequence-dp-4/

  • bishworupmollik
     + 0 comments

    Easiest ||C++||LCS

    int commonChild(string s1, string s2) {

    int n=s1.size();
int m=s2.size();
vector<int>pre(m+2),cur(m+2); //pre is previous row, cur is current row

for(int i=0;i<=n;i++)
{
    for(int j=0;j<=m;j++)
    {
        if(i==0 or j==0)pre[j]=cur[j]=0;

        else if(s1[i-1]==s2[j-1]) cur[j]=pre[j-1]+1;

        else cur[j]=max(pre[j],cur[j-1]);

    }
    pre=cur;

}

return cur[m];

    }