Longest common substring using Dynamic Programming | bottom-up approach

Показать описание

Few years ago, I developed a yearning to grow skills in programming I came across an article which was about the DNA match of two persons.
It was stated in the article that the two DNAs are considered as very very long strings and then the job is to find common substring in two strings, once the
common substring is found the DNAs match.

It intrigued to solve this longest common substring problem on my own. With my limited talent, I came up with a naive solution of finding the longest substring between two strings. It
was working fine when the length of the strings were small but once I tested my program on strings of length beyond 200 chars, my computer jammed.

This poked me to write an optimized algorithm to find the longest common substring. I struggled and struggled until I came across this dynamic programming solution which appeared to me as nothing less than magic.

Here's the description of the problem -

Given two strings
s1 - ABCXYZAY
s2 - XYZABCD

we need to find the length of the longest common substring as well as the common substring between two strings which will be XYZA with length as 4.

This problem is different from longest common subsequence dynamic programming problem as a common substring is characters appearing continuously after one another
whereas, the common subsequence is characters appearing in the some order but not necessarily continuously.

So, let's watch this video to solve the longest common substring problem using dynamic programming.

Рекомендации по теме

Комментарии

awesome! thank you for showing the individual steps in detail.

elshroomness

I think describing the intuition is what helps.

shreyasheranjal

class Solution:
def findLength(self, nums1: List[int], nums2: List[int]) -> int:
n=len(nums1)
m=len(nums2)
dp=[[0]*(n+1) for i in range(m+1)]
for i in range(1, m+1):
for j in range(1, n+1):
if nums1[j-1]==nums2[i-1]:
dp[i][j]=dp[i-1][j-1]+1
else:
dp[i][j]=0
return max(map(max, dp))
to find the length of longest substring

hemanthpidugu

Pls do put questionn link related to video .It would be of really usefull.TIA really great videos

shriramr

Longest common substring using Dynamic Programming | bottom-up approach

DP 27. Longest Common Substring | DP on Strings 🔥

Longest common substring | Dynamic programming

Longest Common Substring | Dynamic Programming | Data Structures And Algorithms | Simplilearn

Longest common substring using Dynamic Programming | bottom-up approach

Longest Common Subsequence - Dynamic Programming - Leetcode 1143

Longest Common Substring Dynamic Programming

Most Asked FAANG Coding Question! | Longest Common Prefix - Leetcode 14

Longest Common Substring

4.9 Longest Common Subsequence (LCS) - Recursion and Dynamic Programming

Longest Common Substring | Dynamic Programming | Intuition and explanation w/ animations

Longest Common Subsequence (2 Strings) - Dynamic Programming & Competing Subproblems

longest common substring using Dynamic programming approach

Sliding Window Algorithm Explained Clearly | Longest Substring Without Repeating Characters Leetcode

Longest common substring #Dynamic Progamming C++ Code

Longest common substring problem suffix array

Longest Common Substring Using Dynamic Programming Tabulation

Longest Common Subsequence

Longest Common Substring (dynamic programming)

Longest Common Substring - using suffix trie

Longest Common Substring Dynamic Programming

DP - 7: Longest common Substring

Longest common substring using dynamic programming

Amazon Coding Interview | Longest Common Substring Dynamic programming | EP6

Longest Common Substring using Suffix Trees