Sort by

recency

|

668 Discussions

|

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

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

    ` def commonChild(s1, s2): # Write your code here matrix = [[0 for j in range(len(s2))] for i in range(len(s1))]

    if s1[0] == s2[0]:
        matrix[0][0] = 1
    else:
        matrix[0][0] = 0
    for j in range(1, len(s2)):
        if s1[0] == s2[j]:
            matrix[0][j] = 1
        else:
            matrix[0][j] = matrix[0][j-1]
    for i in range(1, len(s1)):
        if s2[0] == s1[i]:
            matrix[i][0] = 1
        else:
            matrix[i][0] = matrix[i-1][0]
    
    for i in range(1, len(s1)):
        for j in range(1, len(s2)):
            if s1[i] == s2[j]:
                matrix[i][j] = 1 + matrix[i-1][j-1]
            else:
                matrix[i][j] = max(matrix[i][j-1], matrix[i-1][j])
    
    return matrix[len(s1)-1][len(s2)-1]