这个String可以通过改组其他两个来创建吗？

Question

想象一下我的两个朋友Wendy并给Hunter他们的孩子起个名字Henry.请注意,该名称Henry可以被创建Hunter和Wendy通过合并每个父母的名字的字符的子集(不改变它们的顺序).进一步来说:

"henry"是"hnr"和"ey",每个父母姓名中的字符顺序保持不变.

"hnr"是字符的子集"hunter",其中字符按顺序排列.

我们可以对"ey"和进行类似的观察"wendy".

题:

是否有一种简单的方法可以验证是否可以通过两个父名称生成任何给定名称,而无需为一对夫妇生成所有可能的子名称？

即我可以很容易地检查isSpecialName("Dan", "Jane", "Adam")-是否"Dan"可以通过名称这种方式来创建"Jane"和"Adam",而不需要检查它,所有的合并有序特性的子集"Jane"和"Adam"？

Answer 1

假设我们想证明字符串a是否对字符串b和字符串是特殊的c.

一个重要的发现是,如果a特殊的b和c,然后删除的最后一个字符a,得到了a',它仍然是特殊的b和c.也就是说:

if   isSpecial(a,        b, c) is True
then isSpecial(a[0..-1], b, c) is True

这是次优模式,因此我们可以使用动态编程算法.

让我们来f(i, j, k)代表a[0..i]特殊的b[0..j]和c[0..k].

a[i] == b[j]  => f(i, j, k) sub pattern is f(i-1, j-1, k)
a[i] == c[k]  => f(i, j, k) sub pattern is f(i-1, j, k-1)
otherwise     => f(i, j, k) sub pattern is f(i, j, k-1) & f(i, j-1, k)

我写了一个小程序来验证这个算法.但代码并不像算法那么简洁.

时间复杂O(la*lb*lc),空间复杂O(la*lb*lc)

#include <stdio.h>
#include <string.h>
#include <stdbool.h>
#include <ctype.h>

#define MAX_LEN 10
#define SPECIAL '#'

bool f[MAX_LEN+1][MAX_LEN+1][MAX_LEN+1];

bool isSpecialName(char *pa, char *pb, char *pc) {
    int la = strlen(pa);
    int lb = strlen(pb);
    int lc = strlen(pc);

    if (la > lb + lc) return false;

    memset(f, false, sizeof(f));
    memset(f[0], true, sizeof(f[0]));

    for (int i=1; i<=la; ++i) for (int j=0; j<=lb; ++j) for (int k=0; k<=lc; ++k) {
        char a = tolower(pa[i-1]);
        char b = j > 0 ? tolower(pb[j-1]) : SPECIAL;
        char c = k > 0 ? tolower(pc[k-1]) : SPECIAL;

        if (j > 0)  f[i][j][k] = f[i][j-1][k]   || f[i][j][k];
        if (k > 0)  f[i][j][k] = f[i][j][k-1]   || f[i][j][k];
        if (a == b) f[i][j][k] = f[i-1][j-1][k] || f[i][j][k];
        if (a == c) f[i][j][k] = f[i-1][j][k-1] || f[i][j][k];
    }

    return f[la][lb][lc];
}

void check(char *a, char *b, char *c) {
    if (isSpecialName(a, b, c)) fprintf(stdout, "'%s' *IS* special name of '%s' and '%s'\n", a, b, c);
    else fprintf(stderr, "'%s' is *NOT* special of '%s' and '%s'\n", a, b, c);
}

int main() {
    check("ab", "a", "b");
    check("Dan", "Jane", "Adam");
    check("Henry", "Hunter", "Wendy");
    check("abcd", "ac", "bd");
    check("abcd", "ac", "bb");
    return 0;
}