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

|

669 Discussions

|

  • akshay_vijay123
     + 0 comments

    Python Solution:

    def commonChild(s1, s2):
    dp = [[0] * (len(s2) + 1) for _ in range(len(s1) + 1)]
    
    for i in range(1, len(s1) + 1):
        for j in range(1, len(s2) + 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])
    return dp[len(s1)][len(s2)]

  • maurizioscibilia
     + 0 comments

    python:

    def commonChild(s1, s2):
    # init a DP table with dimensions (len(s1)+1) x (len(s2)+1)
    dp = [[0] * (len(s2) + 1) for _ in range(len(s1) + 1)]
    # filling the DP table
    for i in range(1, len(s1) + 1):
        for j in range(1, len(s2) + 1):
            if s1[i - 1] == s2[j - 1]:
                # match found
                dp[i][j] = dp[i - 1][j - 1] + 1
            else:
                # taking max from previous states
                dp[i][j] = max(dp[i - 1][j], dp[i][j - 1])  
    # at the right-bottom of BP there is the value we want
    return dp[len(s1)][len(s2)]

  • 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);
}