Longest Common Subsequence

Given two strings text1 and text2, return the length of their longest common subsequence. If there is no common subsequence, return 0.

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.

  • For example, "ace" is a subsequence of "abcde".

A common subsequence of two strings is a subsequence that is common to both strings.

 

Example 1:

Input: text1 = "abcde", text2 = "ace" 
Output: 3  
Explanation: The longest common subsequence is "ace" and its length is 3.

Example 2:

Input: text1 = "abc", text2 = "abc"
Output: 3
Explanation: The longest common subsequence is "abc" and its length is 3.

Example 3:

Input: text1 = "abc", text2 = "def"
Output: 0
Explanation: There is no such common subsequence, so the result is 0.

 

Constraints:

  • 1 <= text1.length, text2.length <= 1000
  • text1 and text2 consist of only lowercase English characters.
SOLUTION:
class Solution:
    def lcs(self, text1: str, text2: str, i, j) -> int:
        if (i, j) in self.cache:
            return self.cache[(i, j)]
        if i >= len(text1) or j >= len(text2):
            self.cache[(i, j)] = 0
            return 0
        if text1[i] == text2[j]:
            self.cache[(i, j)] = 1 + self.lcs(text1, text2, i + 1, j + 1)
            return self.cache[(i, j)]
        else:
            a = self.lcs(text1, text2, i + 1, j)
            b = self.lcs(text1, text2, i, j + 1)
            self.cache[(i, j)] = max(a, b)
            return self.cache[(i, j)]
        
    def longestCommonSubsequence(self, text1: str, text2: str, i = 0, j = 0) -> int:
        self.cache = {}
        return self.lcs(text1, text2, 0, 0)

Comments

Post a Comment

Popular posts from this blog

Minimum Number of Operations to Move All Balls to Each Box

You have n boxes. You are given a binary string boxes of length n , where boxes[i] is '0' if the i th box is empty , and '1' if it contains one ball. In one operation, you can move one ball from a box to an adjacent box. Box i is adjacent to box j if abs(i - j) == 1 . Note that after doing so, there may be more than one ball in some boxes. Return an array answer of size n , where answer[i] is the minimum number of operations needed to move all the balls to the i th box. Each answer[i] is calculated considering the initial state of the boxes.   Example 1: Input: boxes = "110" Output: [1,1,3] Explanation: The answer for each box is as follows: 1) First box: you will have to move one ball from the second box to the first box in one operation. 2) Second box: you will have to move one ball from the first box to the second box in one operation. 3) Third box: you will have to move one ball from the first box to the third box in two...
Read more

Efficient Generation of Nth Row of Binomial Coefficient Modulo M

Efficient Generation of Nth Row of Binomial Coefficient Modulo M Efficient Generation of Nth Row of Binomial Coefficient Modulo M Introduction Calculating the binomial coefficient (also known as the combinatorial coefficient) is a common task in mathematics and programming. However, when the modulo M is not prime, finding an efficient method becomes more challenging. In this article, we will explore a technique that allows us to efficiently generate the Nth row of the binomial coefficient modulo M, even when M is not necessarily prime. This technique utilizes prime factorization and a sieve algorithm to achieve efficient computation. The Implementation Let's take a look at the implementation of the technique: from collections import Counter N = 1 + 10 ** 6 v = [False] * N spf = [1] * N for i in range(2, N, 2): spf[i] = 2 for i in range(3, N, 2): if not v[i]: spf[i] = i j = i while j * i 1: ctr[spf[a]...
Read more

Power of Two Difference

Power of Two Difference Power of Two Difference Problem Description Given an integer n , return true if it is a possible difference between powers of two. Otherwise, return false . An integer n is a difference between powers of two if there exist two integers x and y , where x >= y >= 0 , such that n == 2^x - 2^y . Solution Approach The problem can be solved using an elegant solution. We can observe that if n = 2^x - 2^y , then n = 2^y * (2^(x-y) - 1) . Let's call y as M and x - y as N . Now, we observe that 2^N - 1 is a binary number of the form 111...111 , where 1 is repeated N times. Multiplying a binary number by 2^M will add 0 M times to the right. Therefore, our result is of the form 11...1100...00 , where 1 is repeated some times followed by 0 repeated some times or 0 times. For example, 0 is true, 7 is true because it's 111, 12 is true because it's 1100, whereas 5 is false because it's 101 and 13 is false because it's 1101. ...
Read more