Longest Common Sequence Leetcode

We are going to solve a Hard coding Problem longest common sequence leetcode. LeetCode Link of the Problem is HERE. It is one of the most difficult sequence finding tasks on leetcode. We have tried to Solve this in Python3.

Question

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

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".
  • For example, “fbk” is a subsequence of “facebook”
  • For example, “abcde” and “ace” have a common subsequence as “ace”

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

Examples

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

Input: text1 = “abc”, text2 = “abc”
Output: 3
Explanation: The longest common subsequence is “abc” and its length is 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 to longest common sequence leetcode

class Solution(object):
def longestCommonSubsequence(self, s1: str, s2: str) -> int:

  • m,n=len(s1),len(s2)
  • dp=[[0 for i in range(n)] for j in range(m)]
  • for i in range(m):
    • for j in range(n):
      • if s1[i]==s2[j]:
        • if i==0 or j==0:
          • dp[i][j]=1
        • else:
          • dp[i][j]=1+dp[i-1][j-1]
      • 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]

Runtime: 775 ms, faster than 38.71% of Python3 online submissions for Longest Common Subsequence.

Memory Usage: 22.7 MB, less than 57.29% of Python3 online submissions for Longest Common Subsequence.

longest common sequence leetcode· Time: O ( m n ) O(mn) O(mn) · Space: O ( m n ) O(mn) O(mn)..

longest common sequence leetcode

Next Challenges:

Longest Palindromic Subsequence

Delete Operation for Two Strings

Shortest Common Supersequence

Maximize Number of Subsequences in a String

READ MORE

Python-related posts Visit HERE

C++ related posts Visit HERE

Databases related posts Visit HERE

Data Structures related posts visit HERE

Algorithms related posts visit HERE

Data Science related posts visit HERE

Share the Knowledge

1 thought on “Longest Common Sequence Leetcode”

  1. Can I simply say what a comfort to find someone that actually understands what theyre discussing on the net. You actually realize how to bring a problem to light and make it important. More and more people really need to read this and understand this side of your story. I was surprised that youre not more popular since you definitely possess the gift.

Comments are closed.