LeetCode_字符串_简单_1071.字符串的最大公因子

1.题目

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

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

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

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

提示：
1 <= str1.length, str2.length <= 1000
str1 和 str2 由大写英文字母组成

2.思路

（1）枚举

• 首先，通过分析可知，答案肯定是字符串的某个前缀；
• 然后简单直观的想法就是枚举所有的前缀来判断，我们设这个前缀串长度为 lenx；
• 那么我们知道前缀串的长度必然要是两个字符串长度的约数才能满足条件，否则无法经过若干次拼接后得到长度相等的字符串；
• 所以我们可以枚举符合长度条件的前缀串，再去判断这个前缀串拼接若干次以后是否等于 str1 和 str2 即可。

3.代码实现（Java）

//思路1————枚举
class Solution {
    public String gcdOfStrings(String str1, String str2) {
        int len1 = str1.length();
        int len2 = str2.length();
        for (int i = Math.min(len1, len2); i >= 1; i--) {
            if (len1 % i == 0 && len2 % i == 0) {
                String X = str1.substring(0, i);
                if (check(str1, X) && check(str2, X)) {
                    return X;
                }
            }
        }
        return "";
    }

    public boolean check(String s, String t) {
        int lenx = s.length() / t.length();
        StringBuilder res = new StringBuilder();
        for (int i = 1; i <= lenx; i++) {
            res.append(t);
        }
        return res.toString().equals(s);
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25