Longest Common Subsequence (LCS) in DP Playlist

Revision en1, by Algorithms_with_Shayan, 2024-01-13 21:36:04

Hey guys,

I have prepared a video discussing LCS and added it to my YouTube DP playlist.

The Longest Common Substring (LCS) is the length of the longest string shared between two given strings. It's like finding the common set of characters that appear in the same order in both strings.

A subsequence is a sequence of characters that appears in the same order as they do in the original string but not necessarily consecutively. In contrast, a substring is a contiguous sequence of characters within a string.

Here is a code for LCS:


int lcs(string X, string Y) { int m = X.length(); int n = Y.length(); for (int i = 1; i <= m; i++) { for (int j = 1; j <= n; j++) { if (X[i - 1] == Y[j - 1]) dp[i][j] = 1 + dp[i - 1][j - 1]; else dp[i][j] = max(dp[i - 1][j], dp[i][j - 1]); } } return dp[m][n]; }

Link of the DP playlist:

https://www.youtube.com/playlist?list=PLzDmwrrgE-UVKGwxoYao36BVTvBozwLoG

Feel free to join our Discord channel to further discuss these topics and chat with the CP legends I will interview.

https://discord.gg/fYj9xMam7f

As always, please let me know your feedback and suggestions.

Tags lcs, dynamic programming, education, video

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en3 English Algorithms_with_Shayan 2024-01-14 23:22:21 62
en2 English Algorithms_with_Shayan 2024-01-14 17:19:03 87 Tiny change: 'ds&t=634s)\n\n![ ](h' -> 'ds&t=634s).\n\n![ ](h'
en1 English Algorithms_with_Shayan 2024-01-13 21:36:04 1392 Initial revision (published)