对于字符串 S 和 T，只有在 S = T + … + T（T 自身连接 1 次或多次）时，我们才认定 “T 能除尽 S”。
返回最长字符串 X，要求满足 X 能除尽 str1 且 X 能除尽 str2。

示例

示例 1：
输入：str1 = “ABCABC”, str2 = “ABC”
输出：”ABC”

示例 2：

输入：str1 = “ABABAB”, str2 = “ABAB”
输出：”AB”

示例 3：

输入：str1 = “LEET”, str2 = “CODE”
输出：””

题解

假设 str1 与 str2 有公因子，那么 str1 由 N 个 X 组成，str2 由 M 个 X 组成，str1 + str2 与 str2 + str1 必然相等

第二步求2个字符串长度的最大公约数，比如 18 与 12。这里将 18 与 12 相除取余得 6，再将 小数 12 于 6 相除取余。最后余数为0时，最大公约数就是相除的2数中的小数 6

  1. /**
  2.  * @param {string} str1
  3.  * @param {string} str2
  4.  * @return {string}
  5.  */
  6. var gcdOfStrings = function(str1, str2) {
  7.     if (str1 + str2 !== str2 + str1) {
  8.         return ''
  9.     }
  10.     return str1.substr(0, getCommonDivisor(str1.length, str2.length))
  11. };
  13. function getCommonDivisor(a, b) {
  14.     return b === 0 ? a : getCommonDivisor(b, a % b)
  15. }

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/greatest-common-divisor-of-strings
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。