GuilinDev

Lc1071

05 August 2008

1071 Greatest Common Divisor of Strings

题目

For strings 

1

S
and 
1

T
, we say “
1

T
divides 
1

S
” if and only if 
1

S = T + ... + T
(
1

T
concatenated with itself 1 or more times)

Return the largest string 

1

X
such that 
1

X
divides str1 and 
1

X
divides str2.

Example 1:

1
2

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

Example 2:

1
2

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

Example 3:

1
2

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

Note:

  1. 1

    1 <= str1.length <= 1000

  2. 1

    1 <= str2.length <= 1000

  3. 1

    str1[i]
    and 
    1

    str2[i]
    are English uppercase letters.

分析

找两个字符串的最大公约数，依然利用GCD的辗转相除法（Euclidean algorithm），两个字符串如果有不为”“的最大公约字符串，那二者相加的顺序应该时相同的，证明：

  1. 假如s1和s2存在相同的除数X，即s1=XXX, s2=XX, 可见s1+s2=s2+s1
  2. 现在的问题是：若s1和s2不存在相同的除数，那么是否存在s1+s2=s2+s1的情况呢？ 假设s1和s2不存在相同的除数，且满足s1+s2=s2+s1，如下图所示（红色的是s1，蓝色的是s2，其中s1长于s2）

那由上图可知s2既是s1的前缀，又是s2的后缀（灰色表示）。

再看上图的黄色部分可知s3+s2 = s2+s3；其中s3=s1-s2。

以上，我们由s1+s2=s2+s1推出了s3+s2=s2+s3， 其中s3 = s1 - s2。

继而，s3 + s4 = s4 + s3,其中s4 = s3 - s2。

然后可以递归下去，每次用长的减去短的。 因为我们的假设条件是等式s1+s2=s2+s1成立，即上图示成立，所以每次递归时的两个字符串，短串总是长串的前缀和后缀，所以两串总是可减的， 所以我们总是能减到两个串相等的时候，相等时即是最大公共除数，与假设的没有公共除数矛盾。

因此结论是若s1和s2不存在公共除数，则s1+s2!=s2+s1(反之亦然)。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

class Solution {
    public String gcdOfStrings(String str1, String str2) {
        // 假设str1是N个x，str2是M个x，那么concatate后，str1+str2肯定是等于str2+str1的
        if (!(str1 + str2).equals(str2 + str1)) {
            return "";
        }
        
        // 辗转相除法，将两个字符串的长度作为参数，辗转取余，较小的数为0的时候为最大gcd
        return str1.substring(0, gcd(str1.length(), str2.length()));
    }
    
    private int gcd(int a, int b) {
        while (b != 0) {
            int temp = b;
            b = a % b;
            a = temp;
        }
        return a; // 这时b为0
        // return b == 0 ? a: gcd(b, a % b); //递归写法
    }
}
This site is open source. Improve this page.