1071.字符串的最大公因子.md

1071. 字符串的最大公因子

url

题目

对于字符串 S 和 T，只有在 S = T + ... + T（T 自身连接 1 次或多次）时，我们才认定 “T 能除尽 S”。

返回最长字符串 X，要求满足 X 能除尽 str1 且 X 能除尽 str2。

输入：str1 = "ABCABC", str2 = "ABC"
输出："ABC"
输入：str1 = "ABABAB", str2 = "ABAB"
输出："AB"
输入：str1 = "LEET", str2 = "CODE"
输出：""

方法

code

js

let gcdOfStrings = (str1, str2) => {
    if ((str1 + str2) !== (str2 + str1))
        return "";
    return str2.substring(0, gcd(str1.length, str2.length));
};

let gcd = (a, b) => {
  return b === 0 ? a : gcd(b, a % b);
};
console.log(gcdOfStrings("ABCABC", "ABC"));
console.log(gcdOfStrings("ABABAB", "ABAB"));
console.log(gcdOfStrings("LEET", "CODE"));

go

func gcdOfStrings(str1 string, str2 string) string {
	var gcd func(a int, b int) int
	gcd = func (a int, b int) int {
		if b == 0 {
		return a
	} else {
		return gcd(b, a % b)
	}
	}
	if str1+str2 != str2+str1 {
		return ""
	}
	return str2[0:gcd(len(str1), len(str2))]
}

java

class Solution {
    public String gcdOfStrings(String str1, String str2) {
        if (!(str1 + str2).equals(str2 + str1)) {
            return "";
        }
        return str2.substring(0, gcd(str1.length(), str2.length()));
    }

    private int gcd(int a, int b) {
        return b == 0 ? a : gcd(b, a % b);
    }
}