https://leetcode.com/problems/shortest-common-supersequence/
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.
Please review for performance, I am especially interested about the string concatenation part
using System.Text;
using Microsoft.VisualStudio.TestTools.UnitTesting;
namespace StringQuestions
{
/// <summary>
/// https://leetcode.com/problems/shortest-common-supersequence/
/// </summary>
[TestClass]
public class ShortestCommonSuperSequenceTest
{
[TestMethod]
public void TestMethod1()
{
string str1 = "abac";
string str2 = "cab";
string expected = "cabac";
Assert.AreEqual(expected, ShortestCommonSuperSequenceClass.ShortestCommonSupersequence(str1, str2));
}
[TestMethod]
public void TestMethod2()
{
string str1 = "xxx";
string str2 = "xx";
string expected = "xxx";
Assert.AreEqual(expected, ShortestCommonSuperSequenceClass.ShortestCommonSupersequence(str1, str2));
}
[TestMethod]
public void TestMethod3()
{
string str1 = "xxxc";
string str2 = "xxa";
string expected = "xxxca";
Assert.AreEqual(expected, ShortestCommonSuperSequenceClass.ShortestCommonSupersequence(str1, str2));
}
}
public class ShortestCommonSuperSequenceClass
{
public static string ShortestCommonSupersequence(string str1, string str2)
{
if (string.IsNullOrEmpty(str1) || string.IsNullOrEmpty(str2))
{
return string.Empty;
}
int i = 0;
int j = 0;
string lcs = FindLCS(str1, str2);
StringBuilder res = new StringBuilder();
foreach (var letter in lcs)
{
while (str1[i] != letter)
{
res.Append(str1[i]);
i++;
}
while (str2[j] != letter)
{
res.Append(str2[j]);
j++;
}
res.Append(letter);
i++;
j++;
}
return res + str1.Substring(i) + str2.Substring(j);
}
private static string FindLCS(string str1, string str2)
{
string[,] dp = new string[str1.Length + 1, str2.Length + 1];
for (int i = 0; i < str1.Length+1; i++)
{
for (int j = 0; j < str2.Length+1; j++)
{
dp[i, j] = string.Empty;
}
}
for (int i = 0; i < str1.Length; i++)
{
for (int j = 0; j < str2.Length; j++)
{
//remember 0 is 0 always
if (str1[i] == str2[j])
{
dp[i+1, j+1] = dp[i, j] + str1[i];
}
else
{
if (dp[i + 1, j].Length > dp[i, j + 1].Length)
{
dp[i + 1, j + 1] = dp[i + 1, j];
}
else
{
dp[i + 1, j + 1] = dp[i, j + 1];
}
}
}
}
return dp[str1.Length, str2.Length];
}
}
}