Declaração do problema 1768. Mesclar strings alternadamente

Dadas duas strings, palavra1 e palavra2, a tarefa é mesclá-las alternando caracteres. O processo começa com Word1 e continua até que uma string se esgote. Quaisquer caracteres restantes da string mais longa são anexados ao final da string mesclada.

Meu processo de pensamento

Dada a simplicidade do problema, reconheci imediatamente uma abordagem de duas etapas como a solução mais adequada. Meu pseudocódigo inicial descreveu as seguintes etapas:

1.Inicialize dois ponteiros, um para cada string.
2.Iterar ambas as strings, adicionando caracteres alternadamente a uma nova string até que uma string esteja vazia.
3. Anexe os caracteres restantes da string não vazia à nova string.

O que falhou/foi bem-sucedido

Para minha satisfação, essa abordagem passou em todos os casos de teste. A estratégia de dois ponteiros lidou com eficácia com o processo de fusão e a subsequente anexação dos caracteres restantes.

Melhorias

Embora a solução inicial funcionasse, identifiquei uma otimização potencial. Em vez de manter dois ponteiros separados, eu poderia iterar com base no comprimento máximo das duas strings. Ao verificar se o índice atual está dentro dos limites de cada string, posso acrescentar caracteres diretamente sem verificações desnecessárias. Essa abordagem simplificada melhora a eficiência.

Complexidade de tempo e espaço

Complexidade de tempo: O(m n), onde m e n são os comprimentos de Word1 e Word2, respectivamente. Isso ocorre porque iteramos cada caractere em ambas as strings uma vez.
Complexidade do espaço: O(m n) também, já que criamos uma nova string para armazenar o resultado mesclado.