Edit distance variant — shortest common super-sequence

The motivation for this problem came from Steven Skiena :

8–4. The longest common subsequence (LCS) of two sequences T and P is the longest sequence L such that L is a subsequence of both T and P. The shortest common supersequence (SCS) of T and P is the smallest sequence L such that both T and P are a subsequence of L.

1. Give efficient algorithms to find the LCS and SCS of two given sequences

To pick an example : Input: str1 = “abac”, str2 = “cab”
Output: “cabac”

The approach to this problem would be :

Figure out the longest common subsequence between str1 and str2.

Then iterate the strings and the lcs — if a character does not match — add it to the string. Figure out the final result and return it.

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()];
}

More from 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.