元音的最长有序子序列 - 动态规划
Longest Ordered Subsequence of Vowels - Dynamic Programming
给定一个仅由元音组成的字符串，找出给定字符串中最长的子序列，使得它由所有五个元音组成，并且是一个或多个 a，后跟一个或多个 e，再后跟一个或更多 i，后接一个或多个 o，再接一个或多个 u。
如果有多个最长的子序列，打印任意一个。
问题：您能否展示如何将记忆化添加到 soln below/show如何使用 dp 求解？我已经了解了如何递归求解（如下） .我正在寻求帮助以达到 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
输入：str = "aaauuiieeou"
输出：没有可能的子序列
方法：
我们递归地遍历字符串中的所有字符，并遵循给定的条件：
如果子序列为空，则仅当元音为“a”时才将其包含在当前索引处。否则，我们继续下一个索引。
如果当前索引处的元音与子序列中包含的最后一个元音相同，我们将其包含在内。
如果当前索引处的元音是子序列中包含的最后一个元音之后的下一个可能的元音（即 a–> e–> i–> o–> u ），我们有两个选择：要么包含它，要么继续下一个索引。因此，我们选择给出最长子序列的那个。
如果满足上述条件中的none，我们继续下一个索引（以避免子序列中元音的无效排序）。
如果我们已经到达字符串的末尾，我们将检查当前子序列是否有效。如果它是有效的（即如果它包含所有元音），我们 return 它，否则我们 return 一个空列表。
# 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"；没有更多的决定要做。您可能希望对输入字符串进行一些预处理，以 p运行e 关闭更多的调用堆栈。例如，记录每个索引的下一个字符位置，并在您达到最后一个 "u" 后尽早退出。但是，None 这对最坏的情况有帮助，因此使用自下而上的方法迭代重写逻辑将是最佳的。
放在一起，您现在可以输入最大长度为堆栈大小的字符串：
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();
}
以上是获取最长元音子序列的长度。同样可以修改为获取字符串，因为我们将每个字符的计数保存在映射中。
给定一个仅由元音组成的字符串，找出给定字符串中最长的子序列，使得它由所有五个元音组成，并且是一个或多个 a，后跟一个或多个 e，再后跟一个或更多 i，后接一个或多个 o，再接一个或多个 u。
如果有多个最长的子序列，打印任意一个。
问题：您能否展示如何将记忆化添加到 soln below/show如何使用 dp 求解？我已经了解了如何递归求解（如下） .我正在寻求帮助以达到 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
输入：str = "aaauuiieeou" 输出：没有可能的子序列
方法： 我们递归地遍历字符串中的所有字符，并遵循给定的条件：
如果子序列为空，则仅当元音为“a”时才将其包含在当前索引处。否则，我们继续下一个索引。 如果当前索引处的元音与子序列中包含的最后一个元音相同，我们将其包含在内。 如果当前索引处的元音是子序列中包含的最后一个元音之后的下一个可能的元音（即 a–> e–> i–> o–> u ），我们有两个选择：要么包含它，要么继续下一个索引。因此，我们选择给出最长子序列的那个。 如果满足上述条件中的none，我们继续下一个索引（以避免子序列中元音的无效排序）。 如果我们已经到达字符串的末尾，我们将检查当前子序列是否有效。如果它是有效的（即如果它包含所有元音），我们 return 它，否则我们 return 一个空列表。
# 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"；没有更多的决定要做。您可能希望对输入字符串进行一些预处理，以 p运行e 关闭更多的调用堆栈。例如，记录每个索引的下一个字符位置，并在您达到最后一个"u"后尽早退出。但是，None 这对最坏的情况有帮助，因此使用自下而上的方法迭代重写逻辑将是最佳的。
放在一起，您现在可以输入最大长度为堆栈大小的字符串：
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();
}
以上是获取最长元音子序列的长度。同样可以修改为获取字符串，因为我们将每个字符的计数保存在映射中。