Leetcode 1250 Solution

This article provides solution to leetcode question 1250 (longest-common-subsequence).
Categories:
Tags:
Access this page by simply typing in "lcs 1250" in your browser address bar if you have bunnylol configured.

https://leetcode.com/problems/longest-common-subsequence

Solution

import numpy as np

class Solution:
    def longestCommonSubsequence(self, text1: str, text2: str) -> int:
        if len(text1) == 0 or len(text2) == 0:
            return 0

        dp = [[0 for _ in range(len(text2))] for _ in range(len(text1))]

        for i in range(0, len(text1)):
            for j in range(0, len(text2)):
                ch1 = text1[i]
                ch2 = text2[j]

                if ch1 == ch2:
                	dp[i][j] = 1 + (dp[i - 1][j - 1] if i > 0 and j > 0 else 0)
                else:
                    dp[i][j] = max(dp[i - 1][j] if i > 0 else 0, dp[i][j - 1] if j > 0 else 0)
                
        return dp[-1][-1]