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
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 |
/* * @Author: Ajk Palikuqi * * Given two words find the longest common sequence of characters between them */ package iqLib.arrayLib; public class LongestCommonSubSequence { public static int findLongestCommonSubSequence(String firstWord, String secondWord) { int cols = firstWord.length(); int rows = secondWord.length(); int[][] DP = new int[cols][rows]; int longestSubSequence = 0; for (int i = 0; i < cols; ++i) { for (int j = 0; j < rows; ++j) { if (firstWord.charAt(i) == secondWord.charAt(j)) { if (i == 0 || j == 0) { DP[i][j] = 1; } else { DP[i][j] = DP[i-1][j-1] + 1; } if (DP[i][j] > longestSubSequence ) { longestSubSequence = DP[i][j]; } } else { DP[i][j] = 0; } } } return longestSubSequence; } } |
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 🙂
Latest posts by Ajk (see all)
- Find Median from Numbers Array - January 1, 2018
- Find Whether a Number Can Be the Sum of Two Squares - August 12, 2017
- How to Find Two Primes Whose Sum is Equal to a Number N - April 22, 2017