Algorithm Puzzles everyday every week sometimes: Greatest Common Divisor of Strings
Puzzle
Puzzle from leetcode:
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.
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: “”
Solution
First Solution
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
| class Solution:
def isDivideable(self, str1: str, str2: str) -> bool:
return str1 == str2 * (len(str1) // len(str2))
def gcdOfStrings(self, str1: str, str2: str) -> str:
len1 = len(str1)
len2 = len(str2)
if len1 > len2:
prefixs = [str2[0:i] for i in reversed(range(1, len2+1)) if self.isDivideable(str2, str2[0:i])]
check_str = str1
else:
prefixs = [str1[0:i] for i in reversed(range(1, len1+1)) if self.isDivideable(str1, str2[0:i])]
check_str = str2
for prefix in prefixs:
if self.isDivideable(check_str, prefix):
return prefix
return ""
|
T.C. O(N^2)
![]()
Optimized Solution
Instead of listing out all possible prefix, we can get gcd length directly:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
| class Solution:
def isDivideable(self, str1: str, str2: str) -> bool:
return str1 == str2 * (len(str1) // len(str2))
def gcdOfStrings(self, str1: str, str2: str) -> str:
len1 = len(str1)
len2 = len(str2)
gcd_length = math.gcd(len1, len2)
candidate = str1[:gcd_length]
if self.isDivideable(str1, candidate) and self.isDivideable(str2, candidate):
return candidate
return ""
|
T.C. O(N)
![]()
