[LeetCode] 1071. Greatest Common Divisor of Strings

For two strings s and t, we say "t divides s" if and only if s = 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.

Example 1:

Input: str1 = "ABCABC", str2 = "ABC"
Output: "ABC"

Example 2:

Input: str1 = "ABABAB", str2 = "ABAB"
Output: "AB"

Example 3:

Input: str1 = "LEET", str2 = "CODE"
Output: ""

Constraints:

• 1 <= str1.length, str2.length <= 1000
• str1 and str2 consist of English uppercase letters.

字符串的最大公因子。

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

给定两个字符串 str1 和 str2 。返回 最长字符串 x，要求满足 x 能除尽 str1 且 x 能除尽 str2 。

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

这是一道数学题，说是求字符串的最大公因子，其实是需要先求出两个字符串长度的最大公约数然后得到子串。其中求最大公约数 gcd 的函数需要背下来。

注意题目的 corner case，如果两个字符串 A + B != B + A 的话，说明两者是没有公共子串的。

时间O(log min(a, b))

空间O(1)

Java实现

 1 class Solution {
 2     public String gcdOfStrings(String str1, String str2) {
 3         // corner case
 4         if (!str1.concat(str2).equals(str2.concat(str1))) {
 5             return "";
 6         }
 7         int gcdLength = helper(str1.length(), str2.length());
 8         return str1.substring(0, gcdLength);
 9     }
10     
11     private int helper(int a, int b) {
12         while (b != 0) {
13             int temp = b;
14             b = a % b;
15             a = temp;
16         }
17         return a;
18     }
19 }

LeetCode 题目总结