寻找满足特定条件的最小字符串

Question

最近在面试中，我被问到了下面这个问题。

给定一个字符串S，我需要找到另一个字符串S2，使得S2是S的一个子序列，并且S也是S2+reverse(S2)的一个子序列。这里的“+”表示字符串连接。我需要输出给定S情况下S2的最小长度。

我被告知这是一个动态规划问题，但我无法解决它。有人能帮我解决这个问题吗？

编辑-

有没有办法以O(N²)或更少的时间复杂度解决这个问题。

- LTim

---

一个 O(n^3) 的解决方案可行吗？ - Sayakiss

不，我需要比O(n^3)更好的解决方案。 - LTim

Answer 1

这个问题有两个重要方面。

1. 由于我们需要S作为S2+reverse(S2)的子字符串，因此S2的长度至少应为n/2。
2. 在连接S2和reverse（S2）之后，存在字母重复的模式，例如

所以解决方案是从 S 的中心到 S 的结尾检查任何连续的元素。如果找到一个，则检查两侧的元素，如下所示。

现在，如果您能够一直到达字符串的末尾，那么最小元素数量(结果)就是从起点到找到连续元素的点的距离。在这个例子中，它是C，即3。

我们知道，这种情况并不总是发生。也就是说，您可能无法在中心找到连续元素。假设连续元素在中心之后，那么我们可以进行相同的测试。

主字符串

子字符串

连接字符串

现在出现了一个重要的疑问。为什么我们只考虑从中心开始的左侧？答案很简单，连接字符串是由S+reverse(S)组成的。因此，我们可以确定子字符串中的最后一个元素在连接字符串中是连续的。没有任何重复出现在主字符串的前半部分可以给出更好的结果，因为至少我们应该有n个字母在最终连接的字符串中。

现在是关于复杂度的问题： 搜索连续字母的最大复杂度为O(n) 现在迭代地检查两侧的元素可以给出最坏情况下的复杂度为O(n)，即最多n/2次比较。 我们可能会在进行第二次检查时失败多次，因此在复杂度之间存在乘法关系，即O(n*n)。

我认为这是一个正确的解决方案，目前没有发现任何漏洞。

- Ginu Jacob

---

代码怎么样？还有为什么你要像他五岁一样解释呢？ - ossobuko

Answer 2

假设S2是“apple”。那么我们可以得出以下假设：

S2 + reverseS2 >= S >= S2 "appleelppa" >= S >= "apple"

因此，给定的S将包含“apple”，但不超过“appleelppe”。它可能是“appleel”或“appleelpp”。

String S ="locomotiffitomoc";
// as you see S2 string is "locomotif" but 
// we don't know S2 yet, so it's blank
String S2 = "";
for (int a=0; a<S.length(); a++) {
    try {
        int b = 0;
        while (S.charAt(a - b) == S.charAt(a + b + 1))
            b++;
        // if this for loop breaks that means that there is a character that doesn't match the rule
        // if for loop doesn't break but throws an exception we found it.
    } catch (Exception e) {
        // if StringOutOfBoundsException is thrown this means end of the string.
        // you can check this manually of course.
        S2 = S.substring(0,a+1);
        break;
    }
}
System.out.println(S2); // will print out "locomotif"

恭喜你，找到了最小的S2。

- ossobuko

---

子字符串 ≠ 子序列 - Sayakiss

Answer 3

字符串S中的每个字符可以包含在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

- Ante

---

Ante - 我无法理解你的解决方案。你是将字符串作为DP的参数传递吗？你的DP状态是什么？抱歉，我从未使用过Python，所以这段代码让我感到困惑。 - LTim

@LTim 两个方法参数都是字符串。第一个参数是初始字符串S的“尾巴”，从中选择S2的其余部分。第二个参数是要用S2+reverse(S2)覆盖的S的剩余部分。如果找到S2，则该方法返回字符串S2。如果找不到S2，则该方法返回None。 - Ante

你的解决方案似乎效率不高，有没有一种能以O(N^2)或更低的时间复杂度完成的方法？我不需要字符串本身，只需要最小长度。 - LTim

@LTim 要获取覆盖长度，请将行'with_char = S[0] + with_char'更改为'with_char = 1 + with_char'。缓存中的最大元素数量是N^3阶，因为参数S可以有N个不同的值，并且to_cover可以有N*(N-1)/2个值。我认为实际数量要小得多，因为调用序列和to_cover的结构，大约为N^2。缓存可以索引以实现常数访问。基于此，我认为运行时间为O(N^2)，其中N是S的长度。在我的笔记本电脑上，上面的示例运行时间约为23毫秒。如果字符串中有更多不同的字符，则重复次数较少，运行速度更快。 - Ante

嗨@Ante：你的解决方案在abacabca的情况下似乎产生了错误的结果。它返回abcabca，但最小的解决方案是abacab。 - nneonneo

@nneonneo 哎呀，是的，请检查 len(with_char) >= len(without_char) 应该是 len(with_char) <= len(without_char) :-/ 我现在正在更改它。 - Ante