Declaração do problema 1071. Maior divisor comum de strings

Para duas strings s e t, dizemos "t divide s" se e somente se s = t t t ... t t (ou seja, t é concatenado consigo mesmo uma ou mais vezes).

Dadas duas strings str1 e str2, retorne a maior string x de modo que x divida str1 e str2.

Meu processo de pensamento

Mesmo que o leetcode tenha marcado isso como um problema fácil, devo admitir que achei difícil encontrar uma solução imediatamente.

Deixe-me revisar os casos de teste fornecidos pelo leetcode e analisá-los para explicar minha confusão.

Casos de teste

Entrada: str1 = "ABCABC", str2 = "ABC"
Saída: "ABC"

Entrada: str1 = "ABABAB", str2 = "ABAB"
Saída: "AB"

A partir da declaração do problema e do caso de teste 1, determinei que precisamos gerar a maior string ("ABC") concatenando a qual podemos obter as duas strings. (string padrão "ABC" === str2 e "ABC" "ABC" === str1).

No entanto, olhando para o caso de teste 2, percebi rapidamente que meu entendimento não estava correto, pois de acordo com isso eu deveria gerar "ABAB", pois é a string mais longa com a qual posso criar ambas as strings. Mas pulei para o código e comecei a mapear uma solução. (Erro de novato?)

O que falhou/foi bem-sucedido

Só consegui mapear uma solução onde:

1. encontre o GCD de duas strings.
2. itera do comprimento da menor string até o GCD
3. pegue uma substring da menor string para o valor da iteração atual.
4. se ambas as strings contiverem essa substring, retorne essa substring como resposta.
5. se nenhuma string for encontrada, retorne "".

Como você pode ver, minha solução falhou nas strings em que str1 contém str2, mas também contém alguns outros caracteres adicionais. violando o requisito de que s = t t ... t t.

Tive que recorrer à solução do neetcode para obter ajuda. Eu rapidamente entendi meus problemas:

1. Eu estava encontrando o GCD do comprimento da string, NÃO a string em si. Preciso encontrar uma string onde, repetindo essas strings, eu possa criar ambas as strings sem nenhum caractere restante.

2. Percebi por que "ABAB" não pode ser a resposta para o caso de teste 2:

• precisamos encontrar x tal que ele divida ambas as strings igualmente. então, tomando "ABAB" como string, você pode criar str2 completamente, mas para str1 você acaba com "ABABABAB". Você acaba com 2 "AB" extras e não pode dizer que criou str1 completamente combinando x.

• "ABAB" comprimento 4 e "ABABAB" comprimento 6. O GCD das 2 strings = 2. Portanto, a saída precisa ser uma string de comprimento 2.

Saída

Complexidade de tempo e espaço

Complexidade de tempo: No pior caso, iteramos sobre Min(str1,str2) e precisamos recriar str1 e str2 para que seja (str1.length str2.length) então complexidade de tempo geral será O(min(str1,str2) * (str1.comprimento str2.comprimento))

Complexidade do espaço: O(1) pois não precisamos de nenhum espaço adicional.