Início / coding / Perguntas / 78917261
Accepted
John Doe
Asked: 2024-08-27 13:39:11 +0800 CST

Maior subsequência completa de vogais ordenadas

  • 772

Dada uma sequência composta de "a", "e", "i", "o" ou "u", encontre a maior subsequência de vogais em ordem. Por exemplo, se a sequência for "aeiaeiou", então a resposta é 6, tornando a subsequência "aaeiou". Outro exemplo é: "aeiaaioooaauuaeiou" onde a resposta é 10. Uma subsequência completa significa que você precisa ter todas as vogais em ordem, a -> e -> i -> o -> u, mas você pode ter repetições de vogais como "aaeeeeiiooouuu" é válido. Se nenhuma subsequência existir, retorne 0.

Eu criei uma abordagem DP de O(n^2) e estou curioso para saber se existe uma versão mais rápida para esse problema.

def find_longest_dp(vowels):
    n = len(vowels)
    dp = [[0, False] for _ in range(n)]
    prev_vowel = {"a": None, "e": "a", "i": "e", "o": "i", "u": "o"}

    for i in range(n):
        if vowels[i] == "a":
            dp[i] = [1, True]
        
        for j in range(i):
            if dp[j][1] and vowels[j] in {vowels[i], prev_vowel[vowels[i]]}:
                dp[i][0] = max(dp[i][0], dp[j][0] + 1)
                dp[i][1] = True
    
    return max((dp[i][0] for i in range(n) if vowels[i] == 'u'), default=0)
python

1 respostas

  1. Best Answer

    O(n) mantendo o controle do comprimento máximo para cada vogal da última subsequência (por exemplo, maxlen[3]informa o comprimento máximo de uma subsequência ordenada terminando com 'o'):

    def find_longest_dp2(vowels):
    maxlen = [0] * 5
    for v in vowels:
        i = 'aeiou'.find(v)
        maxlen[i] = max(maxlen[:i+1]) + 1
    return max(maxlen)

    Ou se todas as cinco vogais precisam estar na subsequência (como o "completo" no seu título sugere) e você quer que, 0caso tal subsequência não exista (como seu código sugere):

    def find_longest_dp3(vowels):
    maxlen = [0] + [float('-inf')] * 5
    for v in vowels:
        i = '.aeiou'.find(v)
        maxlen[i] = max(maxlen[i-1:i+1]) + 1
    return max(maxlen[5], 0)

    Tente isso online! com testes.

    • 1

relate perguntas