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

|

671 Discussions

|

  • dixivu88
     + 0 comments
        ```


public static int Rec(string s1,string s2,int[][] memo,int i1,int i2){
    if(i1<0||i2<0) return 0;
    if(memo[i1][i2]!=-1) return memo[i1][i2];
    if(s1[i1]==s2[i2]){  memo[i1][i2]=1+Rec(s1,s2,memo,i1-1,i2-1);

      return memo[i1][i2];
    }else
    {
         memo[i1][i2]=Math.Max(Rec(s1,s2,memo,i1,i2-1),Rec(s1,s2,memo,i1-1,i2));

         return memo[i1][i2];
    }
}

public static int commonChild(string s1, string s2)
{

   int[][] dp=new int[s1.Length][];
   for(int i=0;i<s1.Length;i++)
       dp[i]=new int[s2.Length];
   for(int i=0;i<s1.Length;i++){
      for(int j=0;j<s2.Length;j++){
        dp[i][j]=-1;       
      }
   }
   Rec(s1,s2,dp,s1.Length-1,s2.Length-1);

   return dp[s1.Length-1][s2.Length-1];  
}

    `

             This is a recusive aproach with memoization.

  • highsoft_soi
     + 0 comments

    Perl:

    sub commonChild {
    my ($s1, $s2) = @_;
    my $n = length($s1);
    my $m = length($s2);

    my @prev = (0) x ($m + 1);
    my @curr = (0) x ($m + 1);

    for my $i (1 .. $n) {
        for my $j (1 .. $m) {
            if (substr($s1, $i - 1, 1) eq substr($s2, $j - 1, 1)) {
                $curr[$j] = $prev[$j - 1] + 1;
            } else {
                $curr[$j] = $curr[$j - 1] > $prev[$j] ? $curr[$j - 1] : $prev[$j];
            }
        }
        @prev = @curr;
    }
    return $curr[$m];
}

  • 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()