CareerCup

#include <iostream>
#include <list>
#include <string>  
#include <utility>

using namespace std;

typedef pair<string,string> rePair;
typedef list<rePair> rePairList;

bool doMatch(string re, string str) {
  int rePos = re.size() - 1;
  int strPos = str.size() - 1;
  
  while (rePos >= 0 && strPos >= 0) {
    char reChar = re[rePos];
    char strChar = str[strPos];
    
    //Wildcard
    if (reChar == '*') {
      //See if it matches without the wildcard
      bool ret = doMatch(string(re, 0, rePos-1), string(str, 0, strPos+1));
      if (ret) return true;
      
      //No match without it.  match one by one and check again
      //if it matches without the wild.
      while (str[strPos] == re[rePos-1]) {
        strPos--;

        ret = doMatch(string(re, 0, rePos-1), string(str, 0, strPos+1));
        if (ret) return true;
      }
      
      //Pass the wildcard and loop.
      rePos -= 2;
      continue;
    }

    //dot and literal matches
    if (reChar == '.' || (reChar == strChar)) {
      rePos--;
      strPos--;
      continue;
    }

    //Not a match!
    return false;
  }

  //Left at the beginning of both?
  return (rePos < 0 && strPos < 0);
}

int main() {

  rePairList tests;
  tests.push_back(rePair("az*b", "azzzzzb")); //yes
  tests.push_back(rePair("azz*zb", "azzzzzb")); //yes
  tests.push_back(rePair("az*.....z*b", "azzzzzb")); //yes
  tests.push_back(rePair("az*.z*b", "azzzzzb")); //yes
  tests.push_back(rePair("az.b", "azxb")); //yes
  tests.push_back(rePair("azxb", "azxb")); //yes
  tests.push_back(rePair("azxb", "azab")); //no
  
  for (rePairList::iterator it = tests.begin() ; it != tests.end() ; it++) {
    bool ret = doMatch(it->first, it->second);
    cout << it->first << " / " << it->second << " --> " << ret << endl;
  }
  cout << endl << endl << "DONE" << endl;
}

Use automata

My simple recursive solution:

// fwd decls
bool match_dot(const char *r, const char *s);
bool match_star(char c, const char *r, const char *s);

bool match(const char *r, const char *s)
{
	if (*r == 0)
	{
		return *s == 0;
	}
	if (*r == '.')
	{
		return match_dot(r + 1, s);
	}
	if (*(r+1) == '*')
	{
		return match_star(*r, r + 2, s);
	}
	if (*r == *s)
	{
		return match(r + 1, s + 1);
	}
	else
	{
		return false;
	}
}

bool match_dot(const char *r, const char *s)
{
	if (*r == 0) return true;
	while (*s != 0)
	{
		if (match(r, s)) return true;
		s++;
	}
	return false;
}

bool match_star(char c, const char *r, const char *s)
{
	if (*s == c)
	{
		if (match_star(c, r, s + 1)) return true;
	}
	return match(r, s);
}

public class PatternMatcherRegex {
	
	
	public static boolean match(String regX, String candidate) {
		
		//If regex is empty, the pattern doesnt match
		if(regX.isEmpty()) 
			return false;
		
		if(regX.charAt(0) == '*') {
			
			if(regX.length() == 1) {
				/**
				 * The last regex character is *,
				 * which matches everything
				 */
				return true;
			}
			else {
				return matchStar(regX.substring(1), candidate);
			}
			
		}
		else if(candidate.isEmpty()) {
			//Candidate is empty but the pattern is not
			return false;
		} 
		else if(regX.charAt(0) == '.' || regX.charAt(0) == candidate.charAt(0)) {
			
			//Last regex matches last character
			if(regX.length() == 1 && candidate.length() == 1) 
				return true;
			else {
				return match(regX.substring(1), candidate.substring(1));
			}
		}
		else 
			return false;
	}
	
	public static boolean matchStar(String regX, String candidate) {
		
		for(int i = 0; i < candidate.length(); i++) {
			if(match(regX, candidate.substring(i)))
				return true;
		}
		
		return false;
	}
	
	public static void main(String[] args) {
		System.out.println(match("a.b", "accb"));
	}
}