Longest Common Subsequence (LCS) in DP Playlist

Правка en2, от Algorithms_with_Shayan, 2024-01-14 17:19:03

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.

You can watch the video here.

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.

Теги lcs, dynamic programming, education, video

История

 
 
 
 
Правки
 
 
  Rev. Язык Кто Когда Δ Комментарий
en3 Английский Algorithms_with_Shayan 2024-01-14 23:22:21 62
en2 Английский 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 Английский Algorithms_with_Shayan 2024-01-13 21:36:04 1392 Initial revision (published)