The Longest Common Subsequence Code Example

Example 1: longest common subsequence

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

Example 2: 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;  }