为使给定字符串成为已排序的字符串，应删除至少多少个字符

Question

我需要找到使字符串排序所需的最小删除数。在

样本测试用例：

# 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}$

Answer 1

对于许多字符串，当前算法将给出不正确的结果。

我怀疑有更有效的方法来解决这个问题，但这里有一个暴力的解决方案。它生成输入字符串的子集，按长度降序排列。子集中的元素保留原始字符串的顺序。一旦count_deletions找到一个有序的子集，它就会返回它（转换回字符串），以及删除的次数。因此，它找到的解决方案保证不短于任何其他输入字符串排序选择。

请参阅^{} docs了解我使用的各种itertools函数的信息；生成子集的算法是从Recipes部分中的powerset示例派生出来的。

from itertools import chain, combinations

def count_deletions(s):
    for t in chain.from_iterable(combinations(s, r) for r in range(len(s), 0, -1)):
        t = list(t)
        if t == sorted(t):
            return ''.join(t), len(s) - len(t)

# Some test data. 
data = [
    "abcdefg",
    "cba",
    "abcb",
    "vwzyx",
    "zvwzyx",
    "adabcef",
    "fantastic",
]

for s in data:
    print(s, count_deletions(s))

输出

^{pr2}$

这个数据集不足以完全测试为解决这个问题而设计的算法，但我想这是一个不错的起点。：）

---

更新

这是一个python3实现的算法，由萨尔瓦多Dali在链接页面上提到。它比我以前的暴力方法快得多，特别是对于较长的字符串。

我们可以通过对字符串的副本进行排序，然后找到原始字符串的最长公共子序列（LCS）和排序后的字符串来找到排序最长的子序列。Salvador的版本从排序的字符串中删除了重复的元素，因为他希望结果严格递增，但这里不需要这样做。

这段代码只返回所需的删除次数，但是很容易修改它以返回实际排序的字符串。

为了使这个递归函数更有效，它使用了functools中的^{}修饰符。

^{3}$

输出

abcdefg 0
cba 2
abcb 1
vwzyx 2
zvwzyx 3
adabcef 1
fantastic 5