longest common subsequence codefroces

class Solution: def longestCommonSubsequence(self, text1: str, text2: str) -> int: """ text1: horizontally text2: vertically """ dp = [[0 for _ in range(len(text1)+1)] for _ in range(len(text2)+1)] for row in range(1, len(text2)+1): for col in range(1, len(text1)+1): if text2[row-1]==text1[col-1]: dp[row][col] = 1+ dp[row-1][col-1] else: dp[row][col] = max(dp[row-1][col], dp[row][col-1]) return dp[len(text2)][len(text1)]

#include<bits/stdc++.h> using namespace std; const int MAX = 1001; int dp[MAX][MAX]; bool visited[MAX][MAX]; int x, y; string s1, s2; int lcs(int i, int j) { if(i == x || j == y) return 0; if(visited[i][j]) return dp[i][j]; visited[i][j] = true; int ans = 0; if(s1[i] == s2[j]) { ans = max(ans, 1+lcs(i+1, j+1)); } else { ans = max(ans, lcs(i+1, j)); ans = max(ans, lcs(i, j+1)); } dp[i][j] = ans; return ans; } int main() { cin >> x >> y; cin >> s1 >> s2; for(int i=0; i<=x; i++) { for(int j=0; j<=y; j++) { visited[i][j] = false; } } cout << lcs(0, 0); return 0; }

longest common subsequence

int maxSubsequenceSubstring(char x[], char y[], 
                            int n, int m) 
{ 
    int dp[MAX][MAX]; 
  
    // Initialize the dp[][] to 0. 
    for (int i = 0; i <= m; i++) 
        for (int j = 0; j <= n; j++) 
            dp[i][j] = 0; 
  
    // Calculating value for each element. 
    for (int i = 1; i <= m; i++) { 
        for (int j = 1; j <= n; j++) { 
  
            // If alphabet of string X and Y are 
            // equal make dp[i][j] = 1 + dp[i-1][j-1] 
            if (x[j - 1] == y[i - 1]) 
                dp[i][j] = 1 + dp[i - 1][j - 1]; 
  
            // Else copy the previous value in the 
            // row i.e dp[i-1][j-1] 
            else
                dp[i][j] = dp[i][j - 1]; 
        } 
    } 
  
    // Finding the maximum length. 
    int ans = 0; 
    for (int i = 1; i <= m; i++) 
        ans = max(ans, dp[i][n]); 
  
    return ans; 
}

Posted by: Guest on May-31-2020

Code answers related to "longest common subsequence codefroces"

Code answers related to "C++"

Browse Popular Code Answers by Language

Answers for "longest common subsequence codefroces"

Code answers related to "longest common subsequence codefroces"

Code answers related to "C++"

Browse Popular Code Answers by Language

Popular Programming Languages

Advertisements

Company

Compilers

Help

Connect with us