leetcode/Dotnet/Problems/Problem1071.cs at main · mnlcz/leetcode · GitHub

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
using System.Text.RegularExpressions;

namespace Problems;

public sealed class Problem1071
{
    // https://leetcode.com/problems/greatest-common-divisor-of-strings/description/
    public string GcdOfStrings(string str1, string str2)
    {
        var minStr = str1.Length < str2.Length ? str1 : str2;
        var maxStr = minStr == str1 ? str2 : str1;
        var candidate = minStr;

        static bool validGcd(string source, string candidate)
        {
            return source == candidate || source.Length == candidate.Length * Regex.Matches(source, candidate).Count;
        }

        while (candidate.Length > 0)
        {
            if (validGcd(minStr, candidate))
            {
                if (validGcd(maxStr, candidate))
                    return candidate;
            }
            candidate = candidate[0..(candidate.Length - 1)];
        }

        return "";
    }
}