[leetcode] 1071. Greatest Common Divisor of Strings

[leetcode] 1071. Greatest Common Divisor of Strings

Description

For two strings s and t, we say “t divides s” if and only if s = t + … + t (t concatenated with itself 1 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: ""

Example 4:

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

Constraints:

1 <= str1.length <= 10001 <= str2.length <= 1000str1 and str2 consist of English uppercase letters.

分析

题目的意思是：给定两个字符串str1，str2.求字符串的最大公约字符串。这道题我的思路是从短的字符串找公约字符串，然后看是否满足长字符串的要求，也能做出来，但是思路不是很好。一个更好的思路是类似求最大公约数的方式进行递归求解，如代码二。

代码一

class Solution: def gcdOfStrings(self, str1: str, str2: str) -> str: m=len(str1) n=len(str2) if(m>n): str1,str2=str2,str1 for i in range(n,-1,-1): t=str1[:i] t1=str1.replace(t,'') t2=str2.replace(t,'') if(t1==t2 and t1==''): return t return ''

代码二

class Solution: def gcdOfStrings(self, str1: str, str2: str) -> str: m=len(str1) n=len(str2) if(m

参考文献

​​[LeetCode] Python Solution | Euclid’s algorithm | 10 lines | Time Complexity -> 95 % | Space Complexity -> 100%​​

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。