Discussion on Common Child Challenge

Sort by

recency

|

672 Discussions

|

7 days ago+ 0 comments

import java.io.*;
import java.util.*;

public class Solution {
    public int child(String str1, String str2){
        int L[][] = new int[str1.length()+1][str2.length()+1];
        for(int i=0;i<=str1.length();i++){
            for(int j=0;j<=str2.length();j++){
                if(i==0 || j==0)
                    L[i][j]=0;
                else if(str1.charAt(i-1)==str2.charAt(j-1)){
                    L[i][j] = L[i-1][j-1]+1;
                }
                else{
                    L[i][j] = Math.max(L[i-1][j],L[i][j-1]);
                }
            }
        }
        return L[str1.length()][str2.length()];
    }
    public static void main(String[] args){
        Solution ob = new Solution();
        Scanner sc = new Scanner(System.in);
        String str1 = sc.nextLine();
        String str2 = sc.nextLine();
        int ans = ob.child(str1,str2);
        System.out.println(ans);
       
    }
}

1 month ago+ 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.

1 month ago+ 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];
}

2 months ago+ 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)]

3 months ago+ 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)]

Sort by

|

672 Discussions

|

Cookie support is required to access HackerRank

Please signup or login in order to view this challenge