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

|

667 Discussions

|

  • Tusenka
     + 0 comments

    My solution based on https://www.geeksforgeeks.org/longest-common-subsequence-dp-4/:

    def _lcs(s1, s2):
    memo=[[0]*(len(s1)+1) for _ in range((len(s2)+1))]
    for i in range(1, len(s1)+1):
        for j in range(1, len(s2)+1):            
            if s1[i-1]==s2[j-1] :          
                memo[i][j]=memo[i-1][j-1]+1
            else:
                memo[i][j]=max(memo[i-1][j], memo[i][j-1])
    return memo[-1][-1]


def commonChild(s1, s2):
    return _lcs(s1, s2)

if __name__ == '__main__':
    fptr = open(os.environ['OUTPUT_PATH'], 'w')

    s1 = input()

    s2 = input()

    result = commonChild(s1, s2)

    fptr.write(str(result) + '\n')

    fptr.close()

  • quangluan0305201
     + 0 comments

    include

    using namespace std;

    int test(string s1, string s2) { int n1 = s1.length(); int n2 = s2.length(); vector> dp(n1 + 1, vector(n2 + 1, 0));

    for (int i = 1; i <= n1; i++) {
    for (int j = 1; j <= n2; j++) {
        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]);
        }
    }
}

return dp[n1][n2];

    }

    int main() { string s1, s2; cin >> s1 >> s2; cout << test(s1, s2) << endl; return 0; }

  • 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]