Press "Enter" to skip to content

Longest common subsequence

Ajk 0

After my last DP problem, I thought I would try another one. In this problem we are asked to find the longest common subsequence of chars between two words. I tried to follow up on my previous example and build an adjacency matrix from the words length and storing the common subsequence at that point in both words. (i.e. DP[i][j] will point to the longest common subsequence between firstWord truncated at i char and secondWord truncated at j char.)

Hence I tried to code this idea in Java and to my surprise everything fell in place pretty quickly.

Find the Longest Common Subsequence

For more info you can check Longest Common Subsequence on wikipedia!
Hope you guys enjoyed it… and I’ll see you guys next time ;D

The following two tabs change content below.
If you like one of my posts the best way to support is give it a thumbs up, comment, or share it on social media 🙂