我需要找到使字符串排序所需的最小删除数。在
样本测试用例:
# Given Input:
teststr = "abcb"
# Expected output:
1
# Explanation
# In this test case, if I delete last 'b' from "abcb",
# then the remaining string "abc" is sorted.
# That is, a single deletion is required.
# Given Input:
teststr = "vwzyx"
# Expected output:
2
# Explanation
# Here, if I delete 'z' and 'x' from "vwzyx",
# then the remaining string "vwy" is a sorted string.
我尝试了下面的方法,但它给出了超出时间限制的错误。 还有其他办法解决这个问题吗?在
^{pr2}$
对于许多字符串,当前算法将给出不正确的结果。
我怀疑有更有效的方法来解决这个问题,但这里有一个暴力的解决方案。它生成输入字符串的子集,按长度降序排列。子集中的元素保留原始字符串的顺序。一旦
count_deletions
找到一个有序的子集,它就会返回它(转换回字符串),以及删除的次数。因此,它找到的解决方案保证不短于任何其他输入字符串排序选择。请参阅^{} docs 了解我使用的各种
itertools
函数的信息;生成子集的算法是从Recipes部分中的powerset
示例派生出来的。输出
^{pr2}$这个数据集不足以完全测试为解决这个问题而设计的算法,但我想这是一个不错的起点。:)
更新
这是一个python3实现的算法,由萨尔瓦多Dali在链接页面上提到。它比我以前的暴力方法快得多,特别是对于较长的字符串。
我们可以通过对字符串的副本进行排序,然后找到原始字符串的最长公共子序列(LCS)和排序后的字符串来找到排序最长的子序列。Salvador的版本从排序的字符串中删除了重复的元素,因为他希望结果严格递增,但这里不需要这样做。
这段代码只返回所需的删除次数,但是很容易修改它以返回实际排序的字符串。
为了使这个递归函数更有效,它使用了functools中的^{} 修饰符。
^{3}$输出
希望它适用于所有情况:)
相关问题 更多 >
编程相关推荐