ChiPy Algorithms SIGDescription
Given two strings text1 and text2, return the length of their longest common subsequence.
A subsequence of a string is a new string generated from the original string with some characters(can be none) deleted without changing the relative order of the remaining characters. (eg, “ace” is a subsequence of “abcde” while “aec” is not). A common subsequence of two strings is a subsequence that is common to both strings.
If there is no common subsequence, return 0.
Solution
Other solutions can be found on the LeetCode link above.
class Solution:
def __init__(self):
self.matrix = {}
def longestCommonSubsequence(self, P: str, Q: str) -> int:
n = len(P)
m = len(Q)
result = 0
keyy = f'{n - 1},{m - 1}'
if keyy in self.matrix.keys():
return self.matrix[keyy]
# BASE CASE
if n == 0 or m == 0:
result = 0
# CASE 1
elif P[n - 1] == Q[m - 1]:
result = 1 + self.longestCommonSubsequence(P[:-1], Q[:-1])
# CASE 2
elif P[n - 1] != Q[m - 1]:
tmp1 = self.longestCommonSubsequence(P[:-1], Q)
tmp2 = self.longestCommonSubsequence(P, Q[:-1])
result = max(tmp1, tmp2)
self.matrix[f'{n - 1},{m - 1}'] = result
return result