Самая длинная полная подпоследовательность упорядоченных гласных
Дана строка, состоящая из «a», «e», «i», «o» или «u», найдите самую длинную подпоследовательность гласных по порядку. Например, если строка — «aeiaeiou», то ответ — 6, что делает подпоследовательность «aaeiou». Другой пример: «aeiaaioooaauuaeiou», где ответ — 10. Полная подпоследовательность означает, что вам нужно расположить все гласные по порядку: a -> e -> i -> o -> u, но вы можете иметь повторы гласных, например «ааааааааааа» действительно. Если такой подпоследовательности не существует, верните 0.
Я придумал подход DP O(n^2), и мне интересно, есть ли более быстрая версия для этой проблемы.
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)
@RobbyCornelissen, вот полная проблема leetcode.com/problems/longest-substring-of-all-vowels-in-order/…
@RobbyCornelisse Подпоследовательность, а не подстрока (непрерывная)
@ sahasrara62 Но проблема с литкодом связана с смежными подстроками
@RobbyCornelissen Нет, вопрос не лишен ясности. Подпоследовательность — это очень четко определенный термин, и ФП никогда не утверждает, что вопрос исходит из лит-кода.
Что означает слово «полный» в вашем названии? Ничего подобного в приведенной спецификации нет.
Расскажите, что означает dp[i], чтобы лучше понять ваш код.
А если «полный» означает, что все пять гласных должны появиться в подпоследовательности, то что, если такой подпоследовательности не существует? Тогда ваш код возвращает 0, но этого нет в указанной спецификации.
Добавлен некоторый контекст в мой вопрос, но «полный» означает, что подпоследовательность должна содержать все [a, e, i, o, u] и они должны быть упорядочены. Что-то вроде «aaaeeioou» допустимо, а «aeiuo» — нет.
Ответы 1
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)
Попробуйте это онлайн!с тестированием.
Спасибо, find_longest_dp3 это то, что я искал - отличная реализация.
Этот вопрос похож на: Самая длинная упорядоченная подпоследовательность гласных — динамическое программирование. Если вы считаете, что это другое, отредактируйте вопрос, поясните, чем он отличается и/или как ответы на этот вопрос не помогают решить вашу проблему.