Edit distance variant — shortest common super-sequence

  1. Give efficient algorithms to find the LCS and SCS of two given sequences
public String shortestCommonSupersequence(String str1, String str2) {
String lcs = getLcs(str1, str2);
int count1 = 0, count2 = 0;
String result = "";
for(int i = 0; i < lcs.length(); i++) {
while(count1 < str1.length() && str1.charAt(count1) != lcs.charAt(i)) {
result += str1.charAt(count1++);
}
while(count2 < str2.length() && str2.charAt(count2) != lcs.charAt(i)) {
result += str2.charAt(count2++);
}
result += lcs.charAt(i);
count1++;
count2++;
}
return result + str1.substring(count1) + str2.substring(count2);
}

String getLcs(String str1, String str2) {
String[][] dp = new String[str1.length() +1][str2.length()+1];
for(int i = 0; i < dp.length; i++)
Arrays.fill(dp[i], "");
for(int i = 1; i <= str1.length(); i++) {
for(int j = 1; j <= str2.length(); j++) {
char chI = str1.charAt(i-1);
char chJ = str2.charAt(j-1);
if(chI == chJ) {
dp[i][j] = dp[i-1][j-1] + chI;
} else {
dp[i][j] = dp[i-1][j].length() > dp[i][j-1].length() ?
dp[i-1][j] : dp[i][j-1];
}
}
}
return dp[str1.length()][str2.length()];
}

--

--

--

I’m a software engineer with a strong interest in algorithms. I love solving puzzles and love the aha moment of arriving at a solution after hours of struggle.

Love podcasts or audiobooks? Learn on the go with our new app.

Recommended from Medium

LambdaTest: Cross Browser Testing Tool | Devstringx Technologies

Preference of Arrays over other Data Structures

Highlighting a few of Ruby’s built in methods

How to track and manage team capacity effectively

My First? Touch of Rust

How To Organise your first Drupal Community Event, and Slay it! Story of #DCG19.

ADAX dev team, stepping into the Cardano community with a contribution

Type Classes in Scala 2

Get the Medium app

A button that says 'Download on the App Store', and if clicked it will lead you to the iOS App store
A button that says 'Get it on, Google Play', and if clicked it will lead you to the Google Play store
Sweta Barman

Sweta Barman

I’m a software engineer with a strong interest in algorithms. I love solving puzzles and love the aha moment of arriving at a solution after hours of struggle.

More from Medium

LeetCode 53. Maximum Subarray

LeetCode 977. Squares of a Sorted Array

Find the K-Beauty of a Number

Leetcode — 1 problem