Skip to content

1071. Greatest Common Divisor of Strings 👍

  • Time:
  • Space:
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
class Solution {
 public:
  string gcdOfStrings(string str1, string str2) {
    if (str1.length() < str2.length())
      return gcdOfStrings(str2, str1);
    if (str1.find(str2) == string::npos)
      return "";
    if (str2.empty())
      return str1;
    return gcdOfStrings(str2, mod(str1, str2));
  }

 private:
  string mod(string& s1, const string& s2) {
    while (s1.find(s2) == 0)
      s1 = s1.substr(s2.length());
    return s1;
  }
};
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
class Solution {
  public String gcdOfStrings(String str1, String str2) {
    if (str1.length() < str2.length())
      return gcdOfStrings(str2, str1);
    if (!str1.startsWith(str2))
      return "";
    if (str2.isEmpty())
      return str1;
    return gcdOfStrings(str2, mod(str1, str2));
  }

  private String mod(String s1, final String s2) {
    while (s1.startsWith(s2))
      s1 = s1.substring(s2.length());
    return s1;
  }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
class Solution:
  def gcdOfStrings(self, str1: str, str2: str) -> str:
    def mod(s1: str, s2: str) -> str:
      while s1.startswith(s2):
        s1 = s1[len(s2):]
      return s1

    if len(str1) < len(str2):
      return self.gcdOfStrings(str2, str1)
    if not str1.startswith(str2):
      return ''
    if not str2:
      return str1
    return self.gcdOfStrings(str2, mod(str1, str2))