Escreva uma função que retorne o palíndromo mais longo em uma determinada string
por exemplo "ccddcc" na cadeia "abaccddccefe"
Eu pensei em uma solução, mas ela é executada em O (n ^ 2) time
Algo 1:
Passos: É um método de força bruta
Tenha 2 para loopspara i = 1 a i menor que array.length -1
para j = i + 1 a j menor que array.length Desta forma, você pode obter substring de todas as combinações possíveis da matrizTenha uma função palíndromo que verifica se uma sequência é palíndromoso para cada substring (i, j) chama essa função, se for um palíndromo, armazene-o em uma variável de sequênciaSe você encontrar a próxima substring do palíndromo e se for maior que a atual, substitua-a pela atua Finalmente, sua variável de string terá a resposta
Questões: 1. Esse algo é executado no tempo O (n ^ 2
Algo 2:
Inverta a string e armazene-a em uma matriz diferenteAgora, encontre a maior substring correspondente entre a matrizMas isso também é executado no tempo O (n ^ 2)Vocês podem pensar em algo que roda em um tempo melhor. Se possível O (n) time