Greatest Common Divisor of Strings
A missão
Problema
Uma string t divide uma string s quando s é t escrita uma ou mais vezes em sequência. Dadas duas strings a e b, retorne a string mais longa que divide as duas, ou uma string vazia quando nenhuma string divide.
Exemplos
Input: a = "ABCABC", b = "ABC"
Output: "ABC"
Input: a = "ABABAB", b = "ABAB"
Output: "AB"
Por quê: AB divide as duas, enquanto ABAB não divide ABABAB
Input: a = "LOOP", b = "POOL"
Output: ""
Por quê: edge case: as strings não compartilham nenhuma unidade de repetição
Dicas
0 / 3
Se existe um divisor comum t, as duas strings são feitas de cópias de t. O que acontece quando você cola as duas strings uma na outra, em qualquer ordem?
a + b é igual a b + a exatamente quando as duas strings são construídas a partir da mesma unidade. Se as duas forem diferentes, a resposta é vazia.
Quando a + b == b + a, o divisor comum mais longo tem comprimento gcd(len(a), len(b)) e é simplesmente o prefixo de a com esse comprimento.
- Tempo-alvo
- O(len(a) + len(b))
- Espaço-alvo
- O(len(a) + len(b))
Solução
Se as duas strings são cópias de alguma unidade t, então a + b e b + a são o mesmo número de cópias de t e, portanto, são iguais; se as strings não são construídas a partir de uma unidade comum, as duas concatenações diferem em algum ponto, e essa única comparação descarta o caso. Quando elas compartilham uma unidade, todo divisor comum tem um comprimento que divide os dois comprimentos, e o maior comprimento possível, o MDC (GCD) dos dois comprimentos, também funciona, já que um prefixo desse comprimento cobre as duas strings. O algoritmo de Euclides o calcula em O(log n) passos, então a solução inteira custa tempo O(n + m) pela checagem da concatenação e espaço O(n + m).
from math import gcd
def gcd_of_strings(a, b):
if a + b != b + a: # no common building block exists
return ""
return a[:gcd(len(a), len(b))] # the longest block that tiles both
print(gcd_of_strings("ABCABC", "ABC")) # -> ABC
print(gcd_of_strings("ABABAB", "ABAB")) # -> AB
print(gcd_of_strings("LOOP", "POOL")) # -> (empty string)Travou na ideia, e não no código? MDC e Euclides explica isso.