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

|

677 Discussions

|

  • ds1b_1641540100
     + 0 comments

    Code in Python 3

    #!/bin/python3

import math
import os
import random
import re
import sys

#
# Complete the 'commonChild' function below.
#
# The function is expected to return an INTEGER.
# The function accepts following parameters:
#  1. STRING s1
#  2. STRING s2
#

def commonChild(s1, s2):
    # Write your code here
    n=len(s1)
    g=len(s2)
    m=[]
    for i in range(n+1):
        m.append([])
        for _ in range(g+1):
            m[i].append(0)
    for i in range(n):
        for j in range(g):
            if s1[i]==s2[j]:
                m[i+1][j+1]=max(m[i][j]+1,m[i+1][j-1])
                continue
            m[i+1][j+1]=max(m[i+1][j],m[i][j+1])
    return m[-1][-1]

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

  • CYS1B_1720109
     + 0 comments

    Python 3:

    #!/bin/python3

import math
import os
import random
import re
import sys

#
# Complete the 'commonChild' function below.
#
# The function is expected to return an INTEGER.
# The function accepts following parameters:
#  1. STRING s1
#  2. STRING s2
#

def commonChild(s1, s2):
    # Write your code here
    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)]

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

  • vutrantrung14821
     + 0 comments
    def commonChild(s1, s2):
    n=len(s1)
    g=len(s2)
    m=[]
    for i in range(n+1):
        m.append([])
        for _ in range(g+1):
            m[i].append(0)
    for i in range(n):
        for j in range(g):
            if s1[i]==s2[j]:
                m[i+1][j+1]=max(m[i][j]+1,m[i+1][j-1])
                continue
            m[i+1][j+1]=max(m[i+1][j],m[i][j+1])
    return m[-1][-1]

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