LeetCode: Greatest Common Divisor of Strings C#

Question

https://leetcode.com/problems/greatest-common-divisor-of-strings/

For strings S and T, we say "T divides S" if and only if S = T + ... + T (T concatenated with itself 1 or more times)

Return the largest string X such that X divides str1 and X divides str2.
Example 1:

Input: str1 = "ABCABC", str2 = "ABC"
Output: "ABC"
Example 2:

Input: str1 = "ABABAB", str2 = "ABAB"
Output: "AB"
Example 3:

Input: str1 = "LEET", str2 = "CODE"
Output: ""


Note:

1 <= str1.length <= 1000
1 <= str2.length <= 1000
str1[i] and str2[i] are English uppercase letters.

I had 30 minutes to solve this. please review this as a real interview.

what is a red flag, remember code will not be prefect.

using System;
using System.Text;
using Microsoft.VisualStudio.TestTools.UnitTesting;

namespace StringQuestions
{
    /// <summary>
    /// https://leetcode.com/problems/greatest-common-divisor-of-strings/
    /// </summary>
    [TestClass]
    public class GreatestCommonDivisorOfStringsTest
    {
        [TestMethod]
        public void TestMethod1()
        {
            string str1 = "ABABAB";
            string str2 = "ABAB";
            string res = GCDOfStringsclass.GcdOfStrings(str1, str2);
            Assert.AreEqual("AB", res);
        }

        [TestMethod]
        public void TestMethod2()
        {
            string str1 = "ABCDEF";
            string str2 = "ABC";
            string res = GCDOfStringsclass.GcdOfStrings(str1, str2);
            Assert.AreEqual(string.Empty, res);
        }
    }

    public class GCDOfStringsclass
    {
        public static string GcdOfStrings(string str1, string str2)
        {
            int min = Math.Min(str1.Length, str2.Length);

            StringBuilder build = new StringBuilder();
            //build largest prefix
            for (int i = 0; i < min; i++)
            {
                if (str1[i] != str2[i])
                {
                    break;
                }

                build.Append(str1[i]);
            }

            // no common prefix
            string prefix = build.ToString();
            if (prefix.Length == 0)
            {
                return string.Empty;
            }

            while (str1.Length % prefix.Length != 0 || str2.Length % prefix.Length != 0)
            {
                prefix = prefix.Remove(prefix.Length - 1);
                if (prefix.Length == 0)
                {
                    return string.Empty;
                }
            }

            for (int i = 0; i < str1.Length / prefix.Length; i++)
            {
                for (int j = 0; j < prefix.Length; j++)
                {
                    if (str1[j + prefix.Length * i] != prefix[j])
                    {
                        return string.Empty;
                    }
                }
            }

            for (int i = 0; i < str2.Length / prefix.Length; i++)
            {
                for (int j = 0; j < prefix.Length; j++)
                {
                    if (str2[j + prefix.Length * i] != prefix[j])
                    {
                        return string.Empty;
                    }
                }
            }

            return prefix;
        }
    }
}

Martin R · Accepted Answer · 2019-10-15 20:22:15Z

The first step in your method is to determine the longest common prefix. Here it would be sufficient to determine the length of the longest common prefix. Building the prefix string itself is not necessary at this point.

The next step is to decrease that length until it divides both string lengths. An explaining comment would be helpful here. We still don't need the prefix string itself, it suffices to decrease the previously determined prefix length.

Finally you determine if the prefix “divides” both strings. At this point we can build the actual prefix string. Again a short comment could be helpful. Instead of the inner loop I would compare substrings (unless that turns out to be too slow):

var prefix = str1.Substring(0, prefixLength);

// Verify that `str1` is a multiple of `prefix`:
for (int i = 1; i < str1.Length / prefixLength; i++)
{
    if (prefix != str1.Substring(i * prefixLength, prefixLength))
    {
        return string.Empty;
    }
}

// Same for `str2` ...

Note that the loop can start with i = 1 because we already now that both strings start with prefix. Since the same logic is applied to both strings I would also consider to move it to a separate IsMultipleOf function.

Performance: Consider the following example:

str1 = "AAA......A"  //  999 characters
str2 = "AAA......AA" // 1000 characters

Your method builds a prefix string of 999 characters first, and then removes successively all but one character, because 1 is the only length that divides both string lengths.

As mentioned above, this can be improved by updating the prefix length only, but one can still do better:

It is not difficult to see that the length of X must be exactly the greatest common divisor of the lengths of str1 and str2 – and that can be determined efficiently with the Euclidean algorithm.

The implementation would then look like this:

private static int gcd(int a, int b)
{
    // Your favorite implementation of the Euclidean algorithm...
}

public static string GcdOfStrings(string str1, string str2)
{
    var prefixLength = gcd(str1.Length, str2.Length);
    var prefix = str1.Substring(0, prefixLength);

    // Is it a common prefix?
    if (prefix != str2.Substring(0, prefixLength)) {
        return "";
    }

    // Verify that `str1` is a multiple of `prefix` ...
    // Verify that `str2` is a multiple of `prefix` ...

    return prefix;
}

cool man. FYI my answer is one of the fastest answers in LeetCode's site, but as I can see there is always room for improvement! thanks man — Gilad
– Gilad, Commented Oct 15, 2019 at 21:11

Stack Exchange Network

LeetCode: Greatest Common Divisor of Strings C#

1 Answer 1

You must log in to answer this question.

Hot Network Questions

LeetCode: Greatest Common Divisor of Strings C#

1 Answer 1

You must log in to answer this question.

Related

Hot Network Questions