Given two strings str1 and str2, return the shortest string that has both str1 and str2 as subsequences. If multiple answers exist, you may return any of them.
(A string S is a subsequence of string T if deleting some number of characters from T (possibly 0, and the characters are chosen anywhere from T) results in the string S.)
Example 1:
Input: str1 = "abac", str2 = "cab"
Output: "cabac"
Explanation:
str1 = "abac" is a subsequence of "cabac" because we can delete the first "c".
str2 = "cab" is a subsequence of "cabac" because we can delete the last "ac".
The answer provided is the shortest such string that satisfies these properties.
Note:
1 <= str1.length, str2.length <= 1000
str1 and str2 consist of lowercase English letters.
Solution:
class Solution {
public String shortestCommonSupersequence(String str1, String str2) {
String lcs = LCS(str1, str2);
StringBuilder sb = new StringBuilder();
int p1 = 0, p2 = 0;
for (int i = 0; i < lcs.length(); i ++) {
while (p1 < str1.length() && str1.charAt(p1) != lcs.charAt(i)) {
sb.append(str1.charAt(p1 ++));
}
while (p2 < str2.length() && str2.charAt(p2) != lcs.charAt(i)) {
sb.append(str2.charAt(p2 ++));
}
sb.append(lcs.charAt(i));
p1 ++;
p2 ++;
}
sb.append(str1.substring(p1)).append(str2.substring(p2));
return sb.toString();
}
private String LCS(String s1, String s2) {
int m = s1.length(), n = s2.length();
String[][] dp = new String[m + 1][n + 1];
for (int i = 0; i <= m; i ++) {
for (int j = 0; j <= n; j ++) {
dp[i][j] = "";
}
}
for (int i = 1; i <= m; i ++) {
for (int j = 1; j <= n; j ++) {
char a = s1.charAt(i - 1);
char b = s2.charAt(j - 1);
if (a == b) {
dp[i][j] = dp[i - 1][j - 1] + Character.toString(a);
} else {
dp[i][j] = dp[i - 1][j].length() > dp[i][j - 1].length() ? dp[i - 1][j] : dp[i][j - 1];
}
}
}
return dp[m][n];
}
}