Самая длинная упорядоченная подпоследовательность гласных - динамическое программирование

Question

Учитывая строку, состоящую только из гласных, найдите самую длинную подпоследовательность в данной строке так, чтобы она состояла из всех пяти гласных и представляла собой последовательность из одного или нескольких а, за которыми следуют один или несколько е, за которыми следуют один или несколько яс последующим одним или несколькими символами o и последующим одним или несколькими символами u.

Если имеется более одной самой длинной подпоследовательности, выведите любую.

ВОПРОС: можете ли вы показать, какВы добавили бы памятку в soln ниже / покажите, как решить, используя dp? Я видел, как решить рекурсивно (ниже).Я прошу помощи в прибытии в дп Солн.

Примеры:

Входные данные: str = "aeiaaioooaauuaeiou" Выходные данные: {a, a, a, a, a, a, e, i, o, u} Существует два возможных выхода вэтот случай: {a, a, a, a, a, a, e, i, o, u} и, {a, e, i, i, o, o, o, u, u, u}, каждый длины10

Входные данные: str = "aaauuiieeou" Выходные данные: подпоследовательность невозможна

Подход: рекурсивно перебираем все символы в строке и следуем заданным условиям:

Еслиподпоследовательность пуста, мы включаем гласный в текущий индекс, только если это «а».В противном случае мы переходим к следующему индексу.Если гласный в текущем индексе совпадает с последним гласным, включенным в подпоследовательность, мы включаем его.Если гласный в текущем индексе является следующим возможным гласным (т.е. a–> e–> i–> o–> u) после последнего гласного, включенного в подпоследовательность, у нас есть два варианта: либо включить его, либо перейти кследующий индекс.Поэтому мы выбираем тот, который дает самую длинную подпоследовательность.Если ни одно из указанных выше условий не выполняется, мы переходим к следующему индексу (чтобы избежать неправильного упорядочения гласных в подпоследовательности).Если мы достигли конца строки, мы проверяем, действительна ли текущая подпоследовательность или нет.Если оно действительно (т. Е. Если оно содержит все гласные), мы возвращаем его, в противном случае мы возвращаем пустой список.

# Python3 program to find the longest subsequence 
# of vowels in the specified order 

vowels = ['a', 'e', 'i', 'o', 'u'] 

# Mapping values for vowels 
mapping = {'a': 0, 'e': 1, 'i': 2, 'o': 3, 'u': 4} 

# Function to check if given subsequence 
# contains all the vowels or not 
def isValidSequence(subList): 

    for vowel in vowels: 
        if vowel not in subList: 
            return False

    return True

# Function to find the longest subsequence of vowels 
# in the given string in specified order 
def longestSubsequence(string, subList, index): 

    # If we have reached the end of the string, 
    # return the subsequence 
    # if it is valid, else return an empty list 
    if index == len(string): 
        if isValidSequence(subList) == True: 
            return subList 
        else: 
            return [] 

    else: 
        # If there is no vowel in the subsequence yet, 
        # add vowel at current index if it is 'a', 
        # else move on to the next character 
        # in the string 
        if len(subList) == 0: 

            if string[index] != 'a': 
                return longestSubsequence(string, subList, index + 1) 
            else: 
                return longestSubsequence(string, subList + \ 
                            [string[index]], index + 1) 

        # If the last vowel in the subsequence until 
        # now is same as the vowel at current index, 
        # add it to the subsequence 
        elif mapping[subList[-1]] == mapping[string[index]]: 
            return longestSubsequence(string, subList + \ 
                            [string[index]], index + 1) 

        # If the vowel at the current index comes 
        # right after the last vowel 
        # in the subsequence, we have two options: 
        # either to add the vowel in 
        # the subsequence, or move on to next character. 
        # We choose the one which gives the longest subsequence. 
        elif (mapping[subList[-1]] + 1) == mapping[string[index]]: 

            sub1 = longestSubsequence(string, subList + \ 
                                [string[index]], index + 1) 
            sub2 = longestSubsequence(string, subList, index + 1) 

            if len(sub1) > len(sub2): 
                return sub1 
            else: 
                return sub2 

        else: 
            return longestSubsequence(string, subList, index + 1) 

# Driver Code 
if __name__ == "__main__": 

    string = "aeiaaioooauuaeiou"

    subsequence = longestSubsequence(string, [], 0) 
    if len(subsequence) == 0: 
        print("No subsequence possible") 
    else: 
        print(subsequence) 

Вывод: ['a', 'e', ​​'i', 'i ',' o ',' o ',' o ',' u ',' u ',' u ']

Answer 1

Реализация ключа для запоминания вашей функции заключается в том, что вы можете использовать (last_chosen_char, length, index) в качестве вашего ключа напоминания.Другими словами, трактуйте "aaeeeiiioo", i=15 и "aaaaaaaeio", i=15 как идентичные, поскольку их последние выбранные символы, длины и текущие индексы эквивалентны.Подзадачи обоих вызовов будут иметь идентичные решения, и нам нужно только потрудиться вычислить один из них.

Несколько дополнительных замечаний:

• Избегайте глобальных переменных, которые нарушают инкапсуляцию ваших функций,который должен работать как черные ящики и не иметь внешних зависимостей.
• Использовать параметры по умолчанию или вспомогательную функцию, чтобы скрыть ненужные параметры от вызывающей стороны и предложить чистый интерфейс.
• Поскольку списки не могут быть хешируемыми(потому что они изменчивы), я переключился на использование строк.
• После запоминания ваш стек вызовов стал новым узким местом.Вы можете рассмотреть возможность использования циклов для сбора серий дубликатов.Точно так же, выбрав "u", вы можете зациклить и собрать все оставшиеся "u" в строке;нет больше решений, которые будут приняты.Возможно, вы захотите немного предварительно обработать входную строку, чтобы удалить больше стека вызовов.Например, запишите следующую позицию символа для каждого индекса и сделайте залог раньше, когда вы нажмете последний "u".Ничто из этого не помогло бы наихудшему случаю, поэтому оптимальным было бы переписать логику с использованием подхода «снизу вверх».

Теперь, собрав его вместе, вы можете вводить строки вплоть до длиныразмер стека:

def longest_subsequence(string):
    def helper(chosen="", i=0):
        if i == len(string):
            return chosen if set("aeiou").issubset(set(chosen)) else ""

        hashable = (chosen[-1] if chosen else None, len(chosen), i)

        if hashable in memo:
            return memo[hashable]

        if not chosen:
            res = helper("a" if string[i] == "a" else chosen, i + 1)
        elif chosen[-1] == string[i]:
            res = helper(chosen + string[i], i + 1)
        elif mapping[chosen[-1]] + 1 == mapping[string[i]]:
            sub1 = helper(chosen + string[i], i + 1)
            sub2 = helper(chosen, i + 1)

            res = sub1 if len(sub1) > len(sub2) else sub2
        else:
            res = helper(chosen, i + 1)

        memo[hashable] = res
        return res

    mapping = {x: i for i, x in enumerate("aeiou")}
    memo = {}
    return helper()

Вот пример выполнения строки длиной 900 символов:

original: uouoouiuoueaeeiiiaaaouuuueuaiaeaioaaiouaouiaiiaiuuueaueaieeueeuuouioaoaeueoioeoeioiuiaiaoeuuuuauuaiuueiieaauuoieiuoiaiueeeoaeaueaaaiaiiieuaoaiaaoiaoaueouaiiooaeeoioiaoieouuuoeaoaeeaaiuieouaeeooiiuooeauueaoaoaeuoaieauooueeeuiueuaeoeouuuiaoiauiaoiaaeeoeouuuueuiiuueoeeoiieuuuauooeuuaaaueuaaaaoaieaiiuoaoouueeeooiuoieoaueooaaioaeoiiiauuoeiaioeauaueiiaeoueioeiieuoiueoeoueeiuiooaioeooueuioaoaeoaiiiauoooieueoeauaiauauuauoueeauouieeoeoeiaeeeeooooeoaueouuuuiioeeuioueeuiaiueooeueeuuuoooeeuooeuoeeeaiioeeiioauiaeaiuaiauooiioeoeueoeieuueouaeeuuoeuaueeeauiiaoeeaeuieoeiuoooeaeeiuaiauuieouuuiuouiuieieoueiiaoiuioaiououooieiauuuououuiiiuaoeeieueeiuoeiaouoeueieuoiaeuoeiieeeaaaeiaeeoauoaoeuuoiiaaeiuiouueaoeuueeoouiaeeeouiouaaaeiouaaeauauioeoeuiauaeaououoaiuuueuieiaeeaouuueeaaiauoieoioaoiuuaioaiauioueieuuuueiaeeuaoeeoeioeoaiauiiuaouuoouooouaeueaioiaouuiiuauiaaeooeueiuoiuoeeauueuuueuueouiiauiuaoiuuoeuoeeauaeoo    
max subsequence: aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeiiiiiiiiiiiooooouuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuu

Попробуйте!