leetcode
July 28, 2024

Viiisit [LeetCode] - 1071. Greatest Common Divisor of Strings

#php#python#javascript#ruby

keep learning, keep coding!

Problem - Greatest Common Divisor of Strings

For two strings s and t, we say “t divides s“ if and only if s = t + t + t + … + t + t (i.e., t is concatenated with itself one or more times).

Given two strings str1 and str2, return the largest string x such that x divides both str1 and str2.

翻譯蒟蒻

一個字串 t 能整除另一個字串 s 時，意思是 s 可以由數個 t 串聯而成。
例如，如果 s = “ababab” 並且 t = “ab”，那麼我們可以說 t 能整除 s，
因為 s 是由三個 t 串聯而成的 (t + t + t = “ab” + “ab” + “ab”)。
因此，給定兩個字符串 str1 和 str2，目的是要找到一個最大字串 x，
使得 x 能同時整除 str1 和 str2。

Solution - JavaScript

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
var gcdOfStrings = function(str1, str2) {
  let gcd = (a, b) => {
    if (b === 0) {
      return a;
    }
    return gcd(b, a % b);
  }
  let len1 = str1.length;
  let len2 = str2.length;
  let len = gcd(len1, len2);
  if (str1 + str2 === str2 + str1) {
    return str1.slice(0, len);
  } else {
    return "";
  }
};

Solution - Ruby

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
def gcd_of_strings(str1, str2)
  def gcd(a, b)
    return a if b == 0
    gcd(b, a % b)
  end

  len1 = str1.size
  len2 = str2.size

  if str1 + str2 === str2 + str1
    return str1[0..gcd(len1, len2) - 1]
  else
    return ""
  end
end

Solution - PHP

1
2
3
4
5
6
7
function gcdOfStrings($str1, $str2) {
  if ($str1 . $str2 !== $str2 . $str1) return '';
  $gcd = function($a, $b) use (&$gcd) {
    return $b === '' ? $a : $gcd($b, substr($a, 0, strlen($a) % strlen($b)));
  };
  return $gcd($str1, $str2);
}

Solution - Python3

1
2
3
4
5
6
7
8
def gcdOfStrings(self, str1: str, str2: str) -> str:
    if str1 + str2 != str2 + str1:
        return ""
    def gcd(a, b):
        while b:
            a, b = b, a % b
        return a
    return str1[:gcd(len(str1), len(str2))] #  表示取 str1 的前 `gcd(len(str1), len(str2))` 個字

LeetCode 傳送門 - Greatest Common Divisor of Strings