How do I find the greatest common divisor of two strings?

You can find the greatest common divisor by checking possible prefixes and validating if repeating them forms both strings.

What is the time complexity of the Greatest Common Divisor of Strings problem?

The time complexity is O(m + n), where m and n are the lengths of the two strings.

What happens if there is no common divisor string?

If there is no common divisor, the solution is an empty string.

What are some common mistakes when solving the Greatest Common Divisor of Strings problem?

Common mistakes include not verifying that the divisor must be a prefix of both strings or overlooking the empty string case.

How does GhostInterview help with solving the Greatest Common Divisor of Strings problem?

GhostInterview provides guidance on efficient solutions, helps avoid pitfalls, and ensures edge cases like empty results are handled properly.

#1071

Easy

auto_awesome数学·string

LeetCode 题解工作台

字符串的最大公因子

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

数学字符串

题目描述

对于字符串 s 和 t，只有在 s = t + t + t + ... + 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"

输出：""

示例 4：

输入：str1 = "AAAAAB", str2 = "AAA"

输出：""

提示：

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

lightbulb

解题思路

方法一

1

2

3

4

5

6

7

8

9

10

11

12

13

14

class Solution:
    def gcdOfStrings(self, str1: str, str2: str) -> str:
        def check(a, b):
            c = ""
            while len(c) < len(b):
                c += a
            return c == b

        for i in range(min(len(str1), len(str2)), 0, -1):
            t = str1[:i]
            if check(t, str1) and check(t, str2):
                return t
        return ''

speed

复杂度分析

指标	值
时间	O(m + n)
空间	O(m + n)

psychology

面试官常问的追问

外企场景

question_mark
Candidate understands string manipulation and divisibility patterns.
question_mark
Candidate shows awareness of efficiency in checking string prefixes.
question_mark
Candidate demonstrates clear reasoning in validating the divisor.

warning

常见陷阱

外企场景

error
Forgetting that the greatest common divisor must be a prefix of both strings.
error
Not checking for an empty string result when no common divisor is found.
error
Assuming the solution always involves finding a non-empty divisor string.

swap_horiz

进阶变体

外企场景

arrow_right_alt
What if both strings have no common divisor?
arrow_right_alt
What if one string is a multiple of the other, but not a perfect divisor?
arrow_right_alt
How does the problem change if strings contain lower case letters?

help

常见问题

外企场景

继续练习

#1041 困于环中的机器人 #1154 一年中的第几天 #972 相等的有理数