CareerCup

If we are allowed to precompute, for each word of the dictionary we can find all possible subsequences and add them to a map subsequence => indexes of words having the subsequence. The query would extract subsequence out of the pattern, find all words having the subsequence, and check each such word agains the pattern.
If we don't allow to precompute, we can just iterate through the dictionary and check against the pattern (the code below).
Worst case O(n^2 * m^2) time and O(n * m) space.

bool Match(string const &s, string const &p, unordered_map<uint64_t, bool> &memo, int s_start = 0, int p_start = 0)
{
	if (s_start < 0 ||
		s_start > s.size() ||
		p_start < 0 ||
		p_start > p.size() ||
		(s_start == s.size() ^ p_start == p.size()))
	{
		return false;
	}

	if (s_start == s.size() &&
		p_start == p.size())
	{
		return true;
	}

	uint64_t memo_key = ((uint64_t)s_start << 32) | p_start;
	auto it = memo.find(memo_key);
	if (it != memo.end()) {
		return it->second;
	}

	int k = s_start;
	for (int i = p_start; i < p.size(); ++i) {
		if (p[i] == '*') {
			for (int j = k; j <= s.size(); ++j) {
				if (Match(s, p, memo, j, i + 1)) {
					memo[memo_key] = true;
					return memo[memo_key];
				}
			}
			memo[memo_key] = false;
			return memo[memo_key];
		} else {
			if (k >= s.size() ||
				(s[k] != p[i] && p[i] != '.'))
			{
				memo[memo_key] = false;
				return memo[memo_key];
			}
		}
		++k;
	}

	memo[memo_key] = (k == s.size());
	return memo[memo_key];
}

We can use Trie Data Structure for this. We can add all the dict words in trie. And then match each char of pattern in Trie. whenever we get '*' we can search all childnodes of current nodes

@me.samyakjain. If we use a trie of the words as they are, in case of * we'd have to traverse to the bottom of the trie, not only children of the current nodes, since * means 'any number of characters'.

public static void main(String[] args) {

		Trie root = new Trie(' ');
		add(root, "cat");
		add(root, "cats");
		add(root, "and");
		add(root, "sand");
		add(root, "dog");

		boolean ret = match(root, "*t", 0, false);
		System.out.println(ret);
	}

	public static boolean match(Trie node, String match, int index, boolean ismatch) {

		if (node == null)
			return ismatch;
		if (index > match.length() - 1)
			return true;

		char c = match.charAt(index);
		if (c == '*') {
			for (int i = 0; i < 26; i++)
				if (!ismatch)
					ismatch = match(node.next[i], match, index + 1, ismatch)
							|| match(node.next[i], match, index, ismatch);
		} else if (c == '.') {
			for (int i = 0; i < 26; i++)
				if (!ismatch)
					ismatch = match(node.next[i], match, index + 1, ismatch);
		} else {
			if (node.next[c - 'a'] == null)
				return false;
			else
				ismatch = match(node.next[c - 'a'], match, index + 1, ismatch);
		}
		return ismatch;
	}

	public static void add(Trie root, String str) {

		char[] arr = str.toCharArray();
		int n = arr.length;
		int k = 0;
		while (k < n) {
			Trie node = root;
			for (int i = k; i < n; i++) {
				Trie t = node.next[arr[i] - 'a'];
				if (t == null) {
					t = new Trie(arr[i]);
					node.next[arr[i] - 'a'] = t;
				}
				if (i == n - 1)
					t.isEnd = true;
				node = t;
			}
			k++;
		}
	}

	static class Trie {

		char c;
		Trie[] next = new Trie[26];
		boolean isEnd;

		public Trie(char c) {
			this.c = c;
		}
	}

We can define a recursive solution for the problem as

f(P, S, i, j) =
i = |P| and j = |S|, if i = |P| or j = |S|,
f(P, S, i + 1, j + 1), if P[i] = '.',
OR between f(P, S, i + 1, k), for 0 <= k <= |S| - j, if P[i] = '*',
f(P, S, i + 1, j + 1), if P[i] = S[j],
false, otherwise

A direct implementation of above function would be O(|P|!). But it can be observed that it can only be called with |P| + 1 different values for i and |S| + 1 different values for j, given that P and S are fixed. So it's a great candidate for Dynamic Programming!

By using O(|P||S|) extra space, runtime dramatically falls down to O(|P||S|)!, by reusing solutions to instances of f we already calculated.

Below is my implementation in JavaScript. It's O(T |P| |S|) in time, when dict has T strings.

function helper(P, S, i, j, memo){
  if (memo[i][j] === null){
    const p = P[i];
    const c = S[j];
    if (i === P.length || j === S.length){
      return i === P.length && j === S.length;
    }
    else if (p === '.'){
      memo[i][j] = helper(P, S, i + 1, j + 1, memo);
    }
    else if (p === '*'){
      for (let k = 0; k <= S.length - j; k++){
        if (helper(P, S, i + 1, j + k, memo)){
          memo[i][j] = true;
        }
      }
      memo[i][j] = memo[i][j] || false;
    }
    else if (p === c){
      memo[i][j] = helper(P, S, i + 1, j + 1, memo);
    }
    else {
      memo[i][j] = false;
    }
  }
  return memo[i][j];
}

function matches(P, S){
  P = Array.from(P);
  S = Array.from(S);
  const memo = new Array(P.length + 1)
    .fill(
      new Array(S.length + 1)
        .fill(null)
    );

  return helper(P, S, 0, 0, memo);
}

function allMatches(P, dict){
  return dict
    .filter((S) => matches(P, S));
}

const dict = ['cat', 'cats', 'and', 'sand', 'dog'];

console.log(allMatches('*t', dict));
console.log(allMatches('.a*', dict));

I believe the solution below is O(p) + O(n * m), where p is the num of chars in the pattern, n the number of chars in the dict string and m the num of dict strings. I've built a simple FSA to match a string against a regex in one shot.

{ { {
class Regex {
static abstract interface Step {
Step accept(char c);
boolean isSuccess();
}

static abstract class AbstractStep implements Step {
final Step next;

AbstractStep(Step next) {
this.next = next;
}

public boolean isSuccess() {
return false;
}
}

static class Char extends AbstractStep {
char c;

Char(Step next, char c) {
super(next);
this.c = c;
}

public Step accept(char c) {
return c == this.c ? next : FAIL;
}
}

static class AnyChar extends AbstractStep {

AnyChar(Step next) {
super(next);
}

public Step accept(char c) {
return next;
}
}

static class AnySeq extends AbstractStep {

AnySeq(Step next) {
super(next);
}

public Step accept(char c) {
Step s = next.accept(c);
return (s != FAIL) ? s : this;
}

public boolean isSuccess() {
return next.isSuccess();
}
}

static class Start extends AbstractStep {

Start(Step next) {
super(next);
}

public Step accept(char c) { return next.accept(c); }

public boolean isSuccess() { return true; }
};

static Step FAIL = new Step() {
public Step accept(char c) { return this; }
public boolean isSuccess() { return false; }
};
static Step END = new Step() {
public Step accept(char c) { return END; }
public boolean isSuccess() { return true; }
};

static Step parse(Step next, char c) {
switch (c) {
case '.':
return new AnyChar(next);
case '*':
return new AnySeq(next);
default:
return new Char(next, c);
}
}

static Step buildParser(String s) {
char[] chars = s.toCharArray();
Step parser = END;
for (int i = chars.length - 1 ; i >= 0 ; i--) {
parser = parse(parser, chars[i]);
}
parser = new Start(parser);
return parser;
}

static boolean test(Step parser, String s) {
for (char c : s.toCharArray()) {
parser = parser.accept(c);
}
return parser.isSuccess();
}

public static void main(String[] args) {
Step parser = buildParser(args[0]);
for (int i = 1 ; i < args.length ; i++) {
if (test(parser, args[i])) {
System.err.println("String " + args[i] + " matches!");
System.exit(0);
}
}
System.err.println("No match found.");
}

}
} } }