1071. Greatest Common Divisor of Strings

题目信息

题号:

1071

难度:

Easy

主题:

字符串重复、公共基串、最大长度

原题:

LeetCode 1071

重点:

字符串 t 只有在两个输入都能由它重复若干次完整拼接得到时才是公共因子;返回其中最长者

题目重述

若非空字符串 t 重复拼接一次或多次能够恰好得到字符串 s,则称 t 可以整除 s。

给定字符串 str1 和 str2,寻找能够同时整除二者的最长非空字符串并返回。若不存在任何公共因子字符串,返回空字符串。

1 <= str1.length, str2.length <= 1000,两个字符串只包含大写英文字母。

自建示例

两个字符串由同一基串重复不同次数得到:

输入:str1 = "XYXYXY", str2 = "XYXY"
输出:"XY"
解释:两个字符串都由 "XY" 重复得到,并且不存在长度更长、能够完整重复生成二者的公共字符串。

不存在公共基串:

输入:str1 = "ABAB", str2 = "ABBA"
输出:""
解释:两个字符串的字符排列方式不同,没有任何非空字符串能够通过完整重复同时生成它们。