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

|

674 Discussions

|

  • gschoen
     + 0 comments

    Another word for this is "longest common subsequence" (or lcs). The basic algorithm is

    int lcs(char *s1, int i, char *s2, int j) {
    if (i == s1.length || j == s2.length) {
        return 0;
    }
    if (s1[i] == s2[j]) {
        return 1 + lcs(s1, i+1, s2, j+1);
    }
    return max(lcs(s1, i+1, s2, j), lcs(s1, i, s2, j+1);
}

    Called from main with

    return lcs(s1, 0, s2, 0);

    Of course, you will need to use memoization to avoid an exponential run time.

  • cherkashin_i_a
     + 0 comments
    import bisect
from collections import defaultdict, deque
from itertools import chain

def longest_increasing_subsequence_length(s):
    lis, covers, last_cover_members = deque(), defaultdict(list), []
    for c in s:
        i = bisect.bisect_left(last_cover_members, c)
        covers[i].append(c)
        if i >= len(last_cover_members):
            last_cover_members.append(c)
        else:
            last_cover_members[i] = c

    return len(last_cover_members)

def commonChild(s1, s2):
    indices_sorted_rev = defaultdict(list)
    for i in range(len(s2) - 1, -1, -1):
        indices_sorted_rev[s2[i]].append(i)
    indices_of_s1_chars_in_s2_rev_sorted = list( chain.from_iterable( (indices_sorted_rev[c] for c in s1) ) )
    if not indices_of_s1_chars_in_s2_rev_sorted:
        return 0
    return longest_increasing_subsequence_length( indices_of_s1_chars_in_s2_rev_sorted )

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

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