CODEWITHSUNDEEP
algorithmcombinatorics
user5943422
user5943422

Reputation:

Can this String be created by shuffling these other two?

Imagine my two friends Wendy and Hunter name their kid Henry. Notice that the name Henry can be created from Hunter and from Wendy by merging subsets of the characters of each parent's name (without changing their order). More specifically:

"henry" is "hnr" and "ey", where the order of characters within each parent's name remains unchanged.

"hnr" is a subset of the characters in "hunter", where the characters remain in order.

We can make a similar observation of "ey" and "wendy".

Question:

Is there a simple way to verify whether any given name can be generated by two parent names without simply generating all the possible child names for a couple?

i.e. Can I easily check isSpecialName("Dan", "Jane", "Adam") - whether "Dan" can be created in such a fashion by the names "Jane" and "Adam", without having to check it against all the merged ordered character subsets of "Jane" and "Adam"?

Upvotes: 1

Views: 98

Answers (2)

delta
delta

Reputation: 3818

Let's say we want to justify if string a is special for string b and string c.

An important observation is, if a special for b and c, then remove the last character of a, got a', it is still special for b and c. That is to say:

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

This is a sub optimal pattern, so we can use dynamic programming algorithm.

Let f(i, j, k) represents if a[0..i] is special for b[0..j] and 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)

I have written a small c program to verify this algorithm. Code is not as concise as the algorithm though.

Time complexity O(la*lb*lc), space complexity 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;
}

Upvotes: 4

maraca
maraca

Reputation: 8753

There are only two or less possibilities when you start matching from the start: either take the first occurrence in mother's or in father's name. Later occurrences could also work, but if they do, taking the first occurence has to work too. So we can write a pretty simple algorithm:

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;
}

Upvotes: 0

Related Questions