Given two strings S1 and S2. Find the longest common subsequence between S1 and S2. Example: Input- S1 = "ACBEA" S2 = "ADCA" Output- "ACA"
package com.ideserve.virendra.questions; /** * <b>IDeserve <br> * <a href="https://www.youtube.com/c/IDeserve">https://www.youtube.com/c/IDeserve</a> * <br><br> * Longest common subsequence - Dynamic Programming Solution</b><br> * Given two strings S1 and S2. Find the longest common subsequence between S1 and S2. * <br><br> * Example: <br> * Input String: <br> * S1 = "ACBEA" * S2 = "ADCA" * <br> * Output: <br> * ACA * <br><br> * <a href="https://www.youtube.com/watch?v=7KcR7fN4-CA">Longest Common Subsequence Solution Youtube Link</a> * @author Virendra * * */ import java.util.ArrayList; import java.util.List; public class LongestCommonSubsequence { public static void commonSubsequence(String S1, String S2) { int s1_len = S1.length(); int s2_len = S2.length(); final int pick_s1_or_s2 = 0; final int pick_s1 = 1; final int pick_s2 = 2; int match[][] = new int[s1_len][s2_len]; int pointer[][] = new int[s1_len][s2_len]; for(int i=0; i<s1_len; i++) { for(int j=0; j<s2_len; j++) { if(S1.charAt(i) == S2.charAt(j)) //Characters match { if((i==0) || (j==0)) //first row or first column { match[i][j] = 1; //initialize } else { match[i][j] = match[i-1][j-1] + 1; } pointer[i][j] = pick_s1_or_s2; } else //Characters mismatch { if((i > 0 ) && (j > 0)) //neither the first row nor first column { //Refer in ppt :- LCS(ACBE,ADC) = max(LCS(ACB,ADC), LCS(ACBE,AD)) //Thumb rule:- mismatch take max. if not in first row or column. if(match[i-1][j] >= match[i][j-1]) { match[i][j] = match[i-1][j]; pointer[i][j] = pick_s2; //ditch s1's character } else { match[i][j] = match[i][j-1]; pointer[i][j] = pick_s1;//ditch s2's character. } } else if ((i==0) && ( j > 0)) //first row { match[i][j] = match[i][j-1]; pointer[i][j] = pick_s1; } else if((j==0) && (i>0)) //first column { match[i][j] = match[i-1][j]; pointer[i][j] = pick_s2; } } } } //Printing the LCS. int i = s1_len - 1; int j = s2_len - 1; StringBuffer result = new StringBuffer(); while(i>=0 && j>=0) { switch(pointer[i][j]) { //go diagonal and collect the matched character case pick_s1_or_s2: result.append(S1.charAt(i)); i--; j--; break; case pick_s1://go left j--; break; case pick_s2://go up i--; break; } } System.out.println(result.reverse()); } public static void main(String args[]) { commonSubsequence("ACBEA", "ADCA"); } }
Time Complexity is O(n^2)Space Complexity is O(n^2)
Sincere thanks from IDeserve community to Virendra Karappa for compiling current post.
Like IDeserve?Support us by whitelisting IDeserve in your ad-blocker.Thanks,-Team IDeserve