Leetcode 1071. Greatest Common Divisor of Strings

Problem

For two strings s and t, we say “t divides s” if and only if s = t + … + t (i.e., t is concatenated with itself one or more times).

Given two strings str1 and str2, return the largest string x such that x divides both str1 and str2.

Algorithm

Enumerate substrings with decreasing length.

Code

class Solution:
    def gcdOfStrings(self, str1: str, str2: str) -> str:
        Len1 = len(str1)
        Len2 = len(str2)
        for i in range(1, Len2+1):
            Len = Len2 // i
            if Len < 1:
                return ""    
            if Len2 // Len * Len == Len2 and Len1 // Len * Len == Len1:
                buffer = str2[0:Len]
                flag1, flag2 = 1, 1
                for j in range(1, Len1+1):
                    if j * Len > Len1:
                        break;
                    elif buffer != str1[(j-1)*Len:j*Len]:
                        flag1 = 0
                        break
                for j in range(1, Len2+1):
                    if j * Len > Len2:
                        break;
                    elif buffer != str2[(j-1)*Len:j*Len]:
                        flag2 = 0
                        break
                if flag1 and flag2:
                    return buffer
        return ""
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
26