3
\$\begingroup\$

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];
        }
    }
}
\$\endgroup\$
4
\$\begingroup\$

Review of your code

The code is written clearly, I have only a few remarks.

The LeetCode problem description states that both str1 and str2 are non-empty strings, so that this

if (string.IsNullOrEmpty(str1) || string.IsNullOrEmpty(str2))
{
    return string.Empty;
}

is not necessary. On the other hand, if you want to handle empty strings then the above is not correct: The shortest common supersequence of the empty string and "abc" is "abc", not the empty string. So that should be

if (string.IsNullOrEmpty(str1))
{
    return str2;
}
if (string.IsNullOrEmpty(str2))
{
    return str1;
}

Here

int i = 0;
int j = 0;
string lcs = FindLCS(str1, str2);
StringBuilder res = new StringBuilder();
foreach (var letter in lcs) 
{ // ...

I would move the declarations of i and j down to where the variables are needed, i.e. directly before the foreach loop.

The attentive reader of your code will of course quickly figure out that

private static string FindLCS(string str1, string str2)

determines the “longest common subsequence” but I would use a more verbose function name (or add an explaining comment).

Explaining the used algorithm shortly would also be helpful to understand the code, something like

/*
 The longest common subsequence (LCS) of str1 and str2 is computed with 
 dynamic programming. 

 dp[i, j] is determined as the LCS of the initial i characters of str1
 and the initial j characters of str2.

 dp[str1.Length, str2.Length] is then the final result.
 */

On the other hand, this comment is mysterious to me:

//remember 0 is 0 always
if (str1[i] == str2[j])

Performance improvements

str1.Length * str2.Length strings are computed in FindLCS(), and that can be avoided. As explained in Wikipedia: Longest common subsequence problem, is is sufficient to store in dp[i, j] the length of the corresponding longest common subsequence, and not the subsequence itself. When the dp array is filled then the longest common subsequence can be determined by deducing the characters in a “traceback” procedure, starting at dp[str1.Length, str2.Length].

This saves both memory and the time for the string operations.

And this approach can easily be modified to collect the shortest common supersequence instead of the longest common subsequence. That makes your “post processing” in your ShortestCommonSupersequence() function obsolete.

The maximum possible length of the shortest common supersequence is known. Therefore the characters can be collected in an array first, so that string operations and a final string reversing is avoided.

Putting it all together, an implementation could look like this:

public static string ShortestCommonSupersequence(string str1, string str2)
{
    // Handle empty strings:
    if (string.IsNullOrEmpty(str1))
    {
        return str2;
    }
    if (string.IsNullOrEmpty(str2))
    {
        return str1;
    }

    // Dynamic programming: dp[i, j] is computed as the length of the
    // longest common subsequence of str1.Substring(0, i) and
    // str2.SubString(0, j).

    int[,] dp = new int[str1.Length + 1, str2.Length + 1];
    for (int i = 0; i < str1.Length; i++)
    {
        for (int j = 0; j < str2.Length; j++)
        {
            if (str1[i] == str2[j])
            {
                dp[i+1, j+1] = dp[i, j] + 1;
            }
            else
            {
                dp[i + 1, j + 1] = Math.Max(dp[i + 1, j], dp[i, j + 1]);
            }
        }
    }

    // Traceback: Collect shortest common supersequence. Since the
    // characters are found in reverse order we put them into an array
    // first.

    char [] resultBuffer = new char[str1.Length + str2.Length];
    int resultIndex = resultBuffer.Length;
    {
        int i = str1.Length;
        int j = str2.Length;
        while (i > 0 && j > 0)
        {
            if (str1[i - 1] == str2[j - 1])
            {
                // Common character:
                resultBuffer[--resultIndex] = str1[i - 1];
                i--;
                j--;
            }
            else if (dp[i - 1, j] > dp[i, j - 1])
            {
                // Character from str1:
                resultBuffer[--resultIndex] = str1[i - 1];
                i--;
            }
            else
            {
                // Character from str2:
                resultBuffer[--resultIndex] = str2[j - 1];
                j--;
            }
        }
        // Prepend remaining characters from str1:
        while (i > 0)
        {
            resultBuffer[--resultIndex] = str1[i - 1];
            i--;
        }
        // Prepend remaining characters from str2:
        while (j > 0)
        {
            resultBuffer[--resultIndex] = str2[j - 1];
            j--;
        }
    }

    // Create and return result string from buffer.
    return new string(resultBuffer, resultIndex, resultBuffer.Length - resultIndex);
}

Comparison: I ran both implementations on LeetCode

  • Original code: Runtime 372 ms, Memory 48.9 MB.
  • Improved code: Runtime 92 ms, Memory 26.1 MB.
\$\endgroup\$
  • \$\begingroup\$ thank you very much! as always I appreciate it very much \$\endgroup\$ – Gilad Oct 24 at 14:26
3
\$\begingroup\$

There are a few places for improvement (in my opinion), but remember - measure! This was written under an assumption that the code works correctly and we do not need any fancy data structures to perform this task.

Arrays

Declaration

As far as I remember, jagged arrays ([][]) have a better performance than multi dimensional ones ([,]) you could try to measure performance with creating dp as string[][] instead.

String building

Allocation

StringBuilder allocates more memory when it doesn't have any more space to fill. Consider passing an argument to it's constructor to pre allocate needed size. You can easily get an upper bound but average size (optimal?) would require some testing.

Building

For a short strings, string concatenation is faster than using a string builder due to memory allocations. You can take a look here for some magical guidance.

Misc

Split vs Substring

Consider using .Split method instead of Substring, I've never personally see any difference but there is some evidence that it might actually speed up the execution.

Unsafe

You can try to mark your methods as unsafe this will request from the compiler to not check boundaries of the arrays and also will give you access to pointer manipulation. I've seen cases where this improved performance. This might give you a significant performance only with a large number of calls.

General notes

Remember, all Substring or string concatenation allocates a new string. I think you should try to figure out how to do this without strings at all! Remember that in reality, characters are just numbers. In my opinion, the main killer here is string concatenation (as you probably guessed).

\$\endgroup\$
  • \$\begingroup\$ @ManLiN2223 thanks a lot, wonderful \$\endgroup\$ – Gilad Oct 24 at 14:26

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.