1071. Greatest Common Divisor of Strings-字符串的最大公因子

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 <= 1000
• 1 <= str2.length <= 1000
• str1 and str2 consist of English uppercase letters.

Solution in python:

class Solution:
    def gcdOfStrings(self, str1: str, str2: str) -> str:
        def factor(num):
            result = []
            i = 1
            while i < num+1:
                if num % i == 0:
                    result.append(num//i)
                i += 1
            return result
        factor1 = factor(len(str2))
        factor2 = factor(len(str1))
        factor3 = [item for item in factor1 if item in factor2]

        for value in factor3:
            i = 0
            while i < len(str2):
                if str2[0:value] != str2[i:i+value]:
                    break
                else:
                    i += value
            j = 0
            while j < len(str1):
                if str1[0:value] != str1[j:j+value]:
                    break
                else:
                    j += value
            if i == len(str2) and j == len(str1) and str1[0:value] == str2[0:value]:
                return str1[0:value]
        return ""