主页 / coding / 问题 / 78917261
Accepted
John Doe
Asked: 2024-08-27 13:39:11 +0800 CST

最长的有序元音完整子序列

  • 772

给定一个由“a”、“e”、“i”、“o”或“u”组成的字符串，按顺序找到最长的元音子序列。例如，如果字符串是“aeiaeiou”，则答案是 6，从而得到子序列“aaeiou”。另一个示例是：“aeiaaioooaauuaeiou”，其答案是 10。完整的子序列意味着您需要按顺序排列所有元音，a -> e -> i -> o -> u，但您可以重复元音，例如“aaeeeeiiooouuu”是有效的。如果不存在这样的子序列，则返回 0。

我想到了一个 O(n^2) 的 DP 方法，我很好奇是否有更快的版本可以解决这个问题。

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 个回答

  1. Best Answer

    O（n）通过跟踪每个子序列最后一个元音的最大长度（例如，maxlen[3]告诉以'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)

    或者，如果所有五个元音都需要在子序列中（如标题中的“完整”所示），并且您希望0不存在这样的子序列（如您的代码所示）：

    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)

    在线尝试！并进行测试。

    • 1

相关问题