60 lines
1.4 KiB
Markdown
60 lines
1.4 KiB
Markdown
---
|
|
title: leetcode-1071
|
|
date: 2020-03-30 22:03:01
|
|
tags:
|
|
categories: leetcode
|
|
---
|
|
|
|
### 1071. 字符串的最大公因子
|
|
|
|
[题目](https://leetcode-cn.com/problems/greatest-common-divisor-of-strings/)
|
|
|
|
|
|
|
|
<!--more-->
|
|
|
|
|
|
|
|
如果存在这样字符串，那它最大的长度就是这两个字符串长度的最大公约数。
|
|
|
|
|
|
|
|
```python
|
|
class Solution:
|
|
def gcdOfStrings(self, str1: str, str2: str) -> str:
|
|
if str1[0] != str2[0]:
|
|
return ''
|
|
|
|
a = len(str1)
|
|
b = len(str2)
|
|
print(a, b)
|
|
if a < b:
|
|
str1, str2 = str2, str1
|
|
a = len(str1)
|
|
b = len(str2)
|
|
|
|
if not a%b:
|
|
for x in range(0, a//b):
|
|
if str1[x*b:(x+1)*b] != str2:
|
|
return ''
|
|
return str2
|
|
else:
|
|
for x in range(b, 0, -1):
|
|
print(x)
|
|
if x==b or b%x or a%x:
|
|
continue
|
|
for y in range(0, b//x):
|
|
if str2[y*x:(y+1)*x] != str2[b-x:b]:
|
|
return ''
|
|
for y in range(0, a//x):
|
|
if str1[y*x:(y+1)*x] != str2[0:x]:
|
|
return ''
|
|
return str2[0:x]
|
|
# 44 ms 13.9 MB
|
|
```
|
|
|
|
|
|
|
|
官方解答中还给了一种巧妙的解法，如果 str1 + str2 == str2 + str1 的话，[可以证明](https://leetcode-cn.com/problems/greatest-common-divisor-of-strings/solution/zi-fu-chuan-de-zui-da-gong-yin-zi-by-leetcode-solu/)必定存在这样一个字符串，其长度为两个字符串长度的最大公约数。
|
|
|