Solução Palíndromo

0 Flares Facebook 0 0 Flares ×

Solução por Rogério Júnior

Para ver o problema original, clique aqui.

 

O problema é uma DP em que o valor de dp(ini,fim)refere-se ao melhor palíndromo encontrado entre os índices ini e fim (inclusive) da string inicial. Cada estado da DP retorna dois inteiros: qtd (número de caracteres especiais) e tam (tamanho do palíndromo). Seja word a string fornecida na entrada.

Se ini=fim, então o palíndromo terá tamanho 1, e só terá um caractere especial se ini for uma das posições especiais. Se ini==fim-1, então, se as letras forem iguais temos um palíndromo de tamanho 2 e basta contarmos os caracteres especiais (no caso ini ou fim) e, caso sejam diferente, o maior palíndromo tem tamanho 1 (uma das duas) e vai ter 1 caractere especial se uma das letras for especial.

Se word[ini]=word[fim], então podemos usar ou não as letras word[ini] e word[fim] no nosso palíndromo resposta. Se usarmos adicionamos 2 ao tamanho de dp[ini+1][fim=1] e o número de novos caracteres especiais (verificamos word[ini] e word[fim] e adicionamos 1 para cada um que seja especial). Se não as usarmos, vemos o melhor entre usar a letra esquerda (dp[ini][fim-1]) ou a direita (dp[ini+1][fim]).

Se word[ini] \neq word[fim], então não podemos usar as duas letras e voltamos para a segunda opção do caso anterior. Segue o código par melhor entendimento:

 

 

0 Flares Facebook 0 0 Flares ×
0 Flares Facebook 0 0 Flares ×
%d bloggers like this: