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
andstr2
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 Greatest Divisor Strings Commonleetcode greatest divisor strings leetcode greatest divisor common 真题greatest divisor little leetcode greatest divisors insert divisible leetcode greatest three occurrence leetcode common count leetcode ancestor common binary equivalent leetcode whether strings leetcode minimum strings delete leetcode strings ranges count