搜索符合某些条件的最小字符串

Question

最近,我在接受采访时被问到以下问题.

给定字符串S,我需要找到另一个字符串S2,使得S2是S的子序列,并且S是S2 +反向的子序列(S2).这里'+'表示连接.我需要为给定的S输出最小可能的S2长度.

我被告知这是一个动态编程问题,但我无法解决它.有人可以帮我解决这个问题吗？

编辑-

有没有办法在O(N ²)或更少的情况下执行此操作.

Answer 1

S 中的每个字符都可以包含在 S2 中，也可以不包含在 S2 中。这样我们就可以构建尝试两种情况的递归：

• S的第一个字符用于封面，
• S 的第一个字符不用于封面，

并计算这两个覆盖的最小值。为了实现这一点，跟踪已经选择的 S2+reverse(S2) 覆盖了 S 的多少就足够了。

有一些优化，我们知道结果是什么（找到覆盖物，不能有覆盖物），并且如果它不会覆盖某些东西，则不需要将第一个字符用作覆盖物。

简单的Python实现：

cache = {}

def S2(S, to_cover):
    if not to_cover:  # Covered
        return ''
    if not S:         # Not covered
        return None
    if len(to_cover) > 2*len(S):  # Can't cover
        return None
    key = (S, to_cover)
    if key not in cache:
        without_char = S2(S[1:], to_cover)     # Calculate with first character skipped
        cache[key] = without_char
        _f = to_cover[0] == S[0]
        _l = to_cover[-1] == S[0]
        if _f or _l:
            # Calculate with first character used
            with_char = S2(S[1:], to_cover[int(_f):len(to_cover)-int(_l)])
            if with_char is not None:
                with_char = S[0] + with_char  # Append char to result
                if without_char is None or len(with_char) <= len(without_char):
                    cache[key] = with_char
    return cache[key]

s = '21211233123123213213131212122111312113221122132121221212321212112121321212121132'
c = S2(s, s)
print len(s), s
print len(c), c