问题描述
给出一个仅由元音组成的字符串，找到给定字符串中最长的子序列，以使其由所有五个元音组成，并且是一个或多个a，一个或多个e，然后一个或多个i的序列. ，然后是一个或多个o，然后是一个或多个u.
Given a string consisting of only vowels, find the longest subsequence in the given string such that it consists of all five vowels and is a sequence of one or more a’s, followed by one or more e’s, followed by one or more i’s, followed by one or more o’s and followed by one or more u’s.
如果最长的子序列超过一个，则打印任何一个.
If there is more than one longest subsequence, print any one.
问题:您能否在下面显示如何向soln添加备忘录/显示如何使用dp解决问题?我已经看到了如何递归求解(下面).我正在寻求帮助以求助于dp soln.
QUESTION: can u pls show how u would add memoization to soln below/show how to solve using dp? I've seen how to solve recursively (below). I'm asking for help in arriving at dp soln.
示例:
输入: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
Input : str = "aeiaaioooaauuaeiou" Output : {a, a, a, a, a, a, e, i, o, u}There are two possible outputs in this case: {a, a, a, a, a, a, e, i, o, u} and, {a, e, i, i, o, o, o, u, u, u}each of length 10
输入:str ="aaauuiieeou"输出:不可能有子序列
Input : str = "aaauuiieeou"Output : No subsequence possible
方法:我们递归地遍历字符串中的所有字符，并遵循给定条件:
Approach:We loop through all the characters in the string recursively and follow the given conditions:
如果子序列为空，则仅在元音为"a"时才将其包含在当前索引中.否则，我们继续下一个索引.如果当前索引处的元音与子序列中包含的最后一个元音相同，则将其包括在内.如果当前索引处的元音是子序列中包含的最后一个元音之后的下一个可能的元音(即a–> e–> i–> o–> u)，我们有两个选择:要么包含它，要么继续下一个索引.因此，我们选择给出最长子序列的序列.如果以上条件都不满足，我们继续下一个索引(以避免在子序列中元音的无效排序).如果已经到达字符串的末尾，则检查当前子序列是否有效.如果它是有效的(即，如果它包含所有元音)，则返回它，否则返回一个空列表.
If the subsequence is empty, we include the vowel at the current index only if it is ‘a’. Otherwise, we move on to the next index.If the vowel at the current index is same as the last vowel included in the subsequence, we include it.If the vowel at the current index is the next possible vowel (i.e a–> e–> i–> o–> u ) after the last vowel included in the subsequence, we have two options: either include it or move on to the next index. Hence we choose the one which gives the longest subsequence.If none of the above conditions is satisfied, we move on to the next index (to avoid invalid ordering of vowels in the subsequence).If we have reached the end of the string, we check if the current subsequence is valid or not. If it is valid (i.e if it contains all the vowels), we return it, else we return an empty list.
# 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']
Output:['a', 'e', 'i', 'i', 'o', 'o', 'o', 'u', 'u', 'u']
推荐答案
记忆功能的关键实现是可以使用(last_chosen_char, length, index)作为记忆键.换句话说，将"aaeeeiiioo", i=15和"aaaaaaaeio", i=15视为相同，因为它们的最后选择的字符，长度和当前索引是等效的.这两个调用的子问题将具有相同的解决方案，我们只需要麻烦计算其中一个即可.
The key realization for memoizing your function is that you can use (last_chosen_char, length, index) as your memo key. In other words, treat "aaeeeiiioo", i=15 and "aaaaaaaeio", i=15 as identical, because their last chosen characters, lengths and current indices are equivalent. The subproblems of both calls will have identical solutions and we only need to bother computing one of them.
一些补充说明:
- 避免使用全局变量破坏函数的封装，这些变量应像黑盒一样工作，并且没有外部依赖项.
- 使用默认参数或帮助器功能对调用者隐藏不必要的参数并提供干净的界面.
- 由于列表不可散列(因为它们是可变的)，因此我改用字符串.
- 记忆后，您的调用堆栈成为新的瓶颈.您可以考虑使用循环来收集一系列重复项.同样，一旦选择了
"u"，您可能还需要循环并收集字符串中所有剩余的"u".没有更多的决定.您可能希望对输入字符串进行一些预处理，以减少更多的调用堆栈.例如，记录下每个索引的下一个字符位置，并在击中最后一个"u"时尽早保释.不过，这些方法都不会对最坏的情况有所帮助，因此使用自下而上的方法迭代地重写逻辑将是最佳选择.
- Avoid global variables which break encapsulation of your functions, which should work as black boxes and not have external dependencies.
- Use default parameters or a helper function to hide unnecessary parameters from the caller and offer a clean interface.
- Since lists aren't hashable (because they're mutable), I switched to using strings.
- After memoization, your call stack is the new bottleneck. You can consider using loops to collect series of duplicates. Similarly, once you've chosen a
"u", you might as well loop and collect all remaining"u"s in the string; there are no more decisions to be made. You might wish to pre-process the input string a bit to prune off more of the call stack. For example, record the next char position for each index and bail early once you've hit the last"u". None of this would help the worst case, though, so rewriting the logic iteratively using a bottom-up approach would be optimal.
将它们放在一起，现在可以输入不超过堆栈大小的字符串:
Putting it together, you can now input strings up to the length of the stack size:
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个字符的字符串上运行的示例:
Here's an example run on a string of 900 characters:
original: uouoouiuoueaeeiiiaaaouuuueuaiaeaioaaiouaouiaiiaiuuueaueaieeueeuuouioaoaeueoioeoeioiuiaiaoeuuuuauuaiuueiieaauuoieiuoiaiueeeoaeaueaaaiaiiieuaoaiaaoiaoaueouaiiooaeeoioiaoieouuuoeaoaeeaaiuieouaeeooiiuooeauueaoaoaeuoaieauooueeeuiueuaeoeouuuiaoiauiaoiaaeeoeouuuueuiiuueoeeoiieuuuauooeuuaaaueuaaaaoaieaiiuoaoouueeeooiuoieoaueooaaioaeoiiiauuoeiaioeauaueiiaeoueioeiieuoiueoeoueeiuiooaioeooueuioaoaeoaiiiauoooieueoeauaiauauuauoueeauouieeoeoeiaeeeeooooeoaueouuuuiioeeuioueeuiaiueooeueeuuuoooeeuooeuoeeeaiioeeiioauiaeaiuaiauooiioeoeueoeieuueouaeeuuoeuaueeeauiiaoeeaeuieoeiuoooeaeeiuaiauuieouuuiuouiuieieoueiiaoiuioaiououooieiauuuououuiiiuaoeeieueeiuoeiaouoeueieuoiaeuoeiieeeaaaeiaeeoauoaoeuuoiiaaeiuiouueaoeuueeoouiaeeeouiouaaaeiouaaeauauioeoeuiauaeaououoaiuuueuieiaeeaouuueeaaiauoieoioaoiuuaioaiauioueieuuuueiaeeuaoeeoeioeoaiauiiuaouuoouooouaeueaioiaouuiiuauiaaeooeueiuoiuoeeauueuuueuueouiiauiuaoiuuoeuoeeauaeoo
max subsequence: aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeiiiiiiiiiiiooooouuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuu
这篇关于元音的最长排序子序列-动态规划的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持！