LeetCode 1071

July 11, 2024

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 + t + ... + 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.

Solution

First, it is important to know that we don't know which string is larger or smaller. So we must pick a standard, in this solution we will make str1 be longer than str2.

if len(str1) < len(str2):
	str1, str2 = str2, str1

The reason we needed to know which string is smaller is because a substring must be equal or less than in length to the other string. The way we will find a substring is to recursively check if str1 starts with str2 and keep cutting off the matched case until the strings are equal. If substring is not found, return an empty string.

# Base Case
if (str1 == str2):
	return str1
	
# Check if str2 starts with str1 (possible substring)
if (str1.startswith(str2)):
	return self.gcdOfStrings(str1[len(str2)], str2)

# Substring not found
return ""