给定一个仅由元音组成的字符串，找到给定字符串中最长的子序列，使其包含所有五个元音，并且是一个或多个a，后跟一个或多个e，后跟一个或多个i，最后的序列后面跟着一个或多个 o，后面跟着一个或多个 u。
如果有多个最长子序列，则打印任意一个。
如何将记忆添加到下面的解决方案中？
我已经了解了如何递归求解（如下）。
示例：
输入：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 =“aaauuiieou” 输出：不可能有子序列
方法： 我们递归地循环遍历字符串中的所有字符并遵循给定的条件：
如果子序列为空，则仅当元音为“a”时，我们才将其包含在当前索引处。否则，我们继续下一个索引。 如果当前索引处的元音与子序列中包含的最后一个元音相同，则将其包含在内。 如果当前索引处的元音是子序列中包含的最后一个元音之后的下一个可能的元音（即 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']
记忆功能的关键实现是您可以使用
(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
private static int longestSubSeqOfVowels(String input) {
char[] v = { 'a', 'e', 'i', 'o', 'u' };
HashMap<Character, Integer> charCount = new HashMap<Character, Integer>();
char c;
int vCount = -1;
for (int i = 0; i < input.length(); i++) {
c = input.charAt(i);
if (vCount == -1 && c != 'a') {
continue;
}
int value = charCount.get(c) == null ? 0 : charCount.get(c) + 1;
if (value == 0) {
if (c == v[vCount + 1]) {
value = vCount >= 0 ? charCount.get(v[vCount]) + 1 : 1;
vCount++;
}
charCount.put(c, value);
} else {
charCount.put(c, value);
}
}
return charCount.get('u').intValue();
}
上面是获取元音最长子序列的长度。可以修改相同的内容来获取字符串，因为我们在映射中保存每个字符的计数。