algorithm - 这个 String 可以通过洗牌这两个来创建吗？

Question

想象一下我的两个 friend Wendy 和 Hunter 给他们的 child 取名 Henry。请注意，名称 Henry 可以从 Hunter 和 Wendy 通过合并每个 parent 姓名的字符子集(不改变它们的顺序)来创建.更具体地说:

“henry”是“hnr”和“ey”，其中每个 parent 姓名中的字符顺序保持不变。

"hnr" 是 "hunter" 中字符的子集，其中字符保持顺序。

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

问题:

有没有一种简单的方法可以验证任何给定的名字是否可以由两个 parent 的名字生成，而不是简单地为一对夫妇生成所有可能的 child 名字？

即我可以轻松检查 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)

我写了一个小的c程序来验证这个算法。虽然代码没有算法那么简洁。

时间复杂度 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;
}