Given a pattern P, check if the string S follows that pattern.

followsPattern.js

// Given a pattern P, check if the string S follows that pattern.
// e.g. 
//    P = aab
//    S = hellohelloworld
//    -> true
// This a naive brute force solution that runs in O(2^N) where N is the size of S, 
//  I hope there's a better solution.
function followsPattern(P, S) {
    function solve(i, complement) {
        if (i === S.length) {
            if (complement.length === P.length) {
                var mapping = {};
                for (var j = 0; j < P.length; j++) {
                    if (P.charAt(j) in mapping) {
                        if (mapping[P.charAt(j)] !== complement[j]) {
                            return false;
                        }
                    } else {
                        mapping[P.charAt(j)] = complement[j];
                    }
                }
                return true;
            } else {
                return false;
            }
        }
        var sols = [];
        for (var k = 1; k <= S.length - i; k++) {
            var s1 = S.substr(i, k);
            var s2 = complement.slice();
            s2.push(s1);
            if (solve(i + k, s2)) {
                return true;
            }
        }
        return false;
    }
    return solve(0, []);
}
// Returns all the ways you can partition a string S
function partition(S) {
    function solve(i, complement) {
        if (i === S.length) {
            return [complement];
        }
        var sols = [];
        for (var k = 1; k <= S.length - i; k++) {
            var s1 = S.substr(i, k);
            var s2 = complement.slice();
            s2.push(s1);
            var parts = solve(i + k, s2);
            Array.prototype.push.apply(sols, parts);
        }
        return sols;
    }
    return solve(0, []);
}

// Test a pattern
// e.g. test('aa?b*c*', 'aabc')
//      -> true
function test(P, S) {
    function solve(i, j, cmp) {
        // Base cases
        if (i < 0) {
            // if we consumed all the characters in P and S, the test passes.
            return j < 0;
        } else if (j < 0) {
            // If we finished with S, but we still have some characters in P, we need to check 
            // the remaining characters.
            if (cmp === '?' || cmp === '*') {
                return solve(i - 1, j, '');
            }
            if (P.charAt(i) === '?') {
                return solve(i - 1, j, '?');
            }
            if (P.charAt(i) === '*') {
                return solve(i - 1, j, '?');
            }
            return false;
        }
        var currentP = P.charAt(i);
        var currentS = S.charAt(j);
        
        if (cmp === '?') {
            if (currentP === currentS) {
                 // I can either acknowledge the current P[i], S[j] match and align P[i-1] with S[j-1]
                 // or ignore P[i] since `?` means {0,1} and align P[i-1] with  S[j]
                return solve(i - 1, j - 1, '') || solve(i - 1, j, '');
            } else {
                return solve(i - 1, j, '');
            }
        }
        if (cmp === '*') {
            if (currentP === currentS) {
                // I can either acknowledge the current S[j] and align P[i] with S[j-1]
                // assuming the same comparison * or you can ignore the current P[i] since `*`
                // means {0, } and align P[i - 1] with S[j]
                return solve(i, j - 1, '*') || solve(i - 1, j, '');
            } else {
                return solve(i - 1, j, '');
            }
        }
        if (currentP === '?') {
            return solve(i - 1, j, '?');
        }
        if (currentP === '*') {
            return solve(i - 1, j, '*');
        }
        if (currentP === currentS) {
            return solve(i - 1, j - 1, '');
        } else {
            return false;
        }
    }
    return solve(P.length - 1, S.length -1, '');
}