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

Question

想象一下我的两个朋友 Wendy 和 Hunter 给他们的孩子取名 Henry。请注意，名称 Henry 可以从 Hunter 和 Wendy 通过合并每个 parent 名称的字符子集（不改变它们的顺序）来创建。更具体地说：

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

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

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

问题：

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

即我可以轻松检查 isSpecialName("Dan", "Jane", "Adam") - 是否可以通过名称 "Jane" 和 "Adam" 以这种方式创建 "Dan"，而不必针对所有合并的有序字符子集进行检查"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)，space复杂度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;
}

Answer 2

当您从头开始匹配时，只有两种或更少的可能性：取母亲或父亲名字中的第一个匹配项。后来出现的事件也可能有效，但如果他们这样做了，那么第一次出现的事件也必须有效。所以我们可以写一个非常简单的算法：

function isSpecialName(child, mother, father) {
    child = child.toLowerCase();
    mother = mother.toLowerCase();
    father = father.toLowerCase();
    for (let i = 0, x = 0, y = 0; i < child.length; i++) {
        let m = mother.indexOf(child[i], x), f = father.indexOf(child[i], y);
        if (m < 0 && f < 0)
            return false;    
        if (f < 0)
            x = m + 1;
        else if (m < 0)
            y = f + 1;
        else if (isSpecialName(
                    child.substr(i + 1), mother.substr(m + 1), father.substr(y)))
            return true;
        else
            y = f + 1;
    }
    return true;
}

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

Can this String be created by shuffling these other two?

algorithm

combinatorics