CareerCup

If a simple match (i.e. no repetition sign following) just recurse with str.substring(1) and regex.substring(1) IFF match found.
At any given point we either pass down unmodified regex with str.substring(1) OR unmodified str with "*" part taken away.
We need to reduce + to *. For that, if current char matches recurse with str.substring(1) and regex where + is replaced by *.

private boolean isMatched(String regex, String str) {
        if (str.length() == 0) {
            // Match is true when regex is exhausted or it's last char is "*" - allowing optional str
            return regex.length() == 0 || regex.charAt(regex.length() - 1) == '*';
        }

        if (regex.length() == 0) {
            // Match is true only if str is fully consumed
            return str.length() == 0;
        }

        Character curReg = regex.charAt(0);
        Character nextReg = regex.length() >= 2 ? regex.charAt(1) : null;
        Character curStr = str.length() != 0 ? str.charAt(0) : null;

        if (nextReg == null || (nextReg != '*' && nextReg != '+')) {
            // This is a simple match - just take the first char from both regex and str and recurse IFF current match is detected
            return isCharMatched(curReg, curStr) && isMatched(regex.substring(1), str.substring(1));
        } else {
            if (nextReg == '*') {
                // The current regex char is followed by "*" - create 2 branches:
                // - one with unmodified regex and reduced str IFF current match detected - meaning to continue repetition if possible
                // - the other one with reduced regex and unmodified str - meaning to try out the optional nature of "*"
                return (isCharMatched(curReg, curStr) && isMatched(regex, str.substring(1)))
                        || isMatched(regex.substring(2), str);
            } else if (nextReg == '+') {
                // The current regex char is followed by "+" - reduce to 1 branch with "*" instead of "+"
                return isCharMatched(curReg, curStr) && isMatched(curReg + "*" + regex.substring(2), str.substring(1));
            } else {
                return false;
            }
        }
    }

    private boolean isCharMatched(Character regexCh, Character strCh) {
        return regexCh == strCh || (regexCh == '.' && strCh >= 'a' && strCh <='z');

}

You need to construct an NFA to do pattern matching with regular expressions.

Below is the code you can check it it takes the following approach:
a.If currently both the characters match increment both the pointers that is first and second.
b.If currently a * is there then you have to consider either the current character of second string or ignore it.
c.If there is a + then consider the fact such as the previous character of first string is equal to the previous character of second string (if there is only one instance) and then consider both either consider the current character or ignore it.

#include <stdio.h>
#include <stdlib.h>

int stringWildCard(char *first,char *second)
{
    if(*first=='\0'&&*second=='\0')
        return 1;
    else if(*first=='*'&&*(first+1)!='\0'&&*second=='\0')//in case of 'a*' and '' it should return true as a* means 0 or more occurences 
        return 1;
 else if(*first=='*'&&*(first+1)!=*second&&*(first-1)!=*second)
        return 0;
   
    else if(*first=='*')
        return stringWildCard(first+1,second)||stringWildCard(first,second+1);
    else if(*first==*second)
        return stringWildCard(first+1,second+1);
    else if(*first!=*second&&*(first+1)=='*')
        return stringWildCard(first+2,second);
    else if(*first=='+'&&*(first-1)==*(second-1))
        return stringWildCard(first,second+1)||stringWildCard(first+1,second);
    return 0;
}
void test(char *first,char *second)
{
    stringWildCard(first,second)?puts("Yes"):puts("No");
}
int main()
{
    test("a*b", "aaaab");//yes
    test("a+bc*", "bccc");//no
    test("ab+cd*", "abbcdd");//yes
}

as per example 1 in the question, we are having four matching patterns , right.?
ab, aab, aaab, ab

the above four patterns are satisfying a*b .
a is occuring 0 or more times and then single 'b' is at end of the string.
so the output should be 4, right.?

Yes.. thats it.
Cool.. thanks a lot. :)

How can anyone write this code in a 45 min interview? One needs extreme practice and one should have seen such questions earlier. There is no way one can think about the algorithm in the interview, leave alone the edge cases.

can anyone explain why Example 2 output is 0? The pattern a+aabc matches the 2nd string (aaabc), does not it?

Following is my code in python.
1. First the pattern string is converted into a pattern list of tuples.
A) a* becomes (a, True, 0) where True signifies that the # of occurence is "GREATER THAN EQUAL" to 0
B) a+ becomes (a, True, 1) where True signifies that the # of occurence is "GREATER THAN EQUAL" to 1
C) a with no */+ becomes (a, False, 1) meaning that there is no "GREATER THAN" condition but only "EQAUL" condition to 1
a+aabc => [('a', True, 1), ('a', False, 1), ('a', False, 1), ('b', False, 1), ('c', False, 1)]

2. Then the pat list simplified so that we accumulate contiguous occurences of the same character.
=> [('a', True, 3), ('b', False, 1), ('c', False, 1)]

3. Then the resulting pat list is expanded so that either we have exact matches or "*" matches .. there are no "+" matches
=> [('a', False, 1), ('a', False, 1), ('a', False, 1), ('a', True, 0), ('b', False, 1), ('c', False, 1)]

with the expanded pattern list consisting of exact matches and * matches, we iterate over the expanded pattern list and the match_string

def get_pat_list(pat_str, pat_list):
    index=0
    while index < len(pat_str):
        char = pat_str[index]
        if (index + 1) < len(pat_str):
            if pat_str[index+1] == '*':
                pat_list.append((char, True, 0))
                index += 2
            elif pat_str[index+1] == '+':
                pat_list.append((char,True, 1))
                index += 2
            else:
                pat_list.append((char, False, 1))
                index += 1
        else:
            pat_list.append((char, False, 1))
            index += 1

    return

def simplify_pat_list(pat_list, simplified_pat_list):
    #simplified_pat_list = list()
    index = 0

    while index < len(pat_list):
        cur_char, acc_ge, acc_val = pat_list[index]

        while ((index+1) < len(pat_list)) and (pat_list[index+1][0] == cur_char):
            acc_ge  |= pat_list[index+1][1]
            acc_val += pat_list[index+1][2]
            index += 1

        simplified_pat_list.append((cur_char, acc_ge, acc_val))
        index += 1

    return  simplified_pat_list
        
        
def expand_pat_list(simplified_pat_list, expanded_pat_list):
    #expanded_pat_list = list()

    for char, ge, val in simplified_pat_list:
        if not ge:
            expanded_pat_list.append((char, ge, val))
        elif val == 0 :
            expanded_pat_list.append((char, ge, val))
        else:
            for i in range(1,val+1):
                expanded_pat_list.append((char, False, 1))

            expanded_pat_list.append((char, True, 0))
            
    return expanded_pat_list
            

def match_pat(expanded_pat_list, match_str):
    index_pat = 0;
    index_mat = 0;
  
    while (index_mat < len(match_str)) and (index_pat < len(expanded_pat_list)):
        if expanded_pat_list[index_pat][1]:
            while (index_mat < len(match_str) and expanded_pat_list[index_pat][0] == match_str[index_mat]):
                #print "INFO0: "+expanded_pat_list[index_pat][0]+" =>" + match_str[index_mat]
                index_mat += 1
            #print "INFO2: "+expanded_pat_list[index_pat][0]+" =>" + match_str[index_mat]
            index_pat += 1

        elif expanded_pat_list[index_pat][0] == match_str[index_mat]:
            #print "INFO1: "+match_str[index_mat]
            index_mat += 1
            index_pat += 1
        else:
            print "ERROR: pattern does not match\n"
            return

    if index_mat == len(match_str) and index_pat == len(expanded_pat_list):
        print "MATCH\n"
    elif index_mat == len(match_str) and index_pat < len(expanded_pat_list):
        while index_pat < len(expanded_pat_list):
            if not expanded_pat_list[index_pat][1]:
                print "ERROR: pattern does not match\n";
            index_pat += 1
        print "Match\n"
    else:
        print "ERROR: pattern does not match\n"
            
            
            
        

        

## MAIN
pat_str = 'a+aabc'
mat_str = "aaaabc"

pat_list = list()
simplified_pat_list = list()
expanded_pat_list = list()

get_pat_list(pat_str, pat_list)
simplify_pat_list(pat_list, simplified_pat_list)
expand_pat_list(simplified_pat_list, expanded_pat_list)

print pat_str
print pat_list
print simplified_pat_list
print expanded_pat_list
print "\n\n";

match_pat(expanded_pat_list, mat_str)

Just wrote a solution using NFA in Java:

import java.util.ArrayList;
import java.util.HashMap;

public class Main {

    public static void main(String[] args) {
        NFA nfa = buildNfa("test+");
        System.out.println(nfa.match("test"));
    }

    private static NFA buildNfa(String s) {

        if (s.length() == 0) {
            return new NFA(new NFA.NFAState(true));
        }
        else {
            char curChar = s.charAt(0);
            if (s.length() == 1) {
                NFA.NFAState state = new NFA.NFAState(true);
                NFA.NFAState entry = new NFA.NFAState(false);
                entry.addTransition(curChar, state);
                return new NFA(entry);
            }
            else {
                char nextChar = s.charAt(1);
                if (nextChar == '+' || nextChar == '*') {
                    NFA.NFAState entry = new NFA.NFAState(nextChar == '*');
                    NFA nfa = buildNfa(s.substring(2));
                    nfa.getEntry().addTransition(curChar, nfa.getEntry());
                    entry.addTransition(curChar, nfa.getEntry());
                    return new NFA(entry);
                }
                else {
                    NFA.NFAState entry = new NFA.NFAState(false);
                    NFA nfa = buildNfa(s.substring(1));
                    entry.addTransition(curChar, nfa.getEntry());
                    return new NFA(entry);
                }
            }
        }
    }

    public static class NFA {
        private NFAState mEntry;

        public NFA(NFAState entry) {
            mEntry = entry;
        }

        public NFAState getEntry() {
            return mEntry;
        }

        public boolean match(String string) {
            if (string == null || string.length() == 0) {
                return mEntry.mIsFinal;
            }
            else {
                Character c = string.charAt(0);
                ArrayList<NFAState> states = mEntry.mTransitions.get(c);
                if (states != null) {
                    for (NFAState state: states) {
                        NFA nfa = new NFA(state);
                        if (nfa.match(string.substring(1))) {
                            return true;
                        }
                    }
                }
                return false;
            }
        }

        public static class NFAState {
            public NFAState(boolean isFinal) {
                mIsFinal = isFinal;
            }

            public void addTransition(Character c, NFAState state) {
                ArrayList<NFAState> transitions = mTransitions.get(c);
                if (transitions == null) {
                    transitions = new ArrayList<NFAState>();
                }
                transitions.add(state);
                mTransitions.put(c, transitions);
            }

            private HashMap<Character, ArrayList<NFAState>> mTransitions = new HashMap<Character, ArrayList<NFAState>>();
            private boolean mIsFinal = false;
        }
    }

}

Here is my solution

#include <iostream>
#include <string>

using namespace std;



bool reStringMatching( string str, string pat) {
    int i, j;
 for(i=0, j = 0; i < str.size() && j < pat.size(); ) {
     cout << "i=" << i << "  j=" << j << endl;
     if(str[i] == pat[j]) {
        i++;j++; continue;  
     } else {
         //* case
         if( j+1 < pat.size() && pat[j+1]=='*') {
  //           cout << "mismatch and j+1 = *" << endl;
             if(j + 2 < pat.size()) {
                 j+=2; continue;
             } else {
                 return false;
             }
         } else if( pat[j]=='*' || pat[j]=='+') {  //* and + case
             if(pat[j-1]==str[i]) {
                 if(i+1 < str.size()) { i++; continue;} 
                 else {return true;}
             } else { // pass * and +
                if (j+1 < pat.size() ) {j++; continue;} 
                else return false;
             }
         } else {
             return false;
         }
     }
 }    
 
 return true;
}

int main()
{
   cout << "Hello World" << endl; 
   cout <<  reStringMatching( string("aaab"), string("a*b")) << endl;
   cout <<  reStringMatching( string("aaaabbab"), string("aa*b*ab+")) << endl;  
   cout <<  reStringMatching( string("ababbc"), string("aa*b*ab+")) << endl;
   cout <<  reStringMatching( string("acccc"), string("aa*b*ab+")) << endl;   
   cout <<  reStringMatching( string("aabab"), string("aa*b*ab+")) << endl;      
   cout <<  reStringMatching( string("aaaabbab"), string("aa*b*ab+")) << endl;   
    
   
   /*
Output if a given pattern matches a string. 
Example: 
pattern:a*b 
string:aaab b, ab, aab, aaab, ab 
output:1 

pattern:a+aabc 
string:ab aabc, aaabc, aaaabc .. 
output:0 

pattern:aa*b*ab+ 
string:aab aab, aabab, aaaabbab 
output:1 

pattern: a+a*b* 
string: a ab, aab, aaabb 
output: 1 
   */
   return 0;
}

I think your code will not work for

aab aa*b*ab+

And it will give yes for

aab aa*b*ac+

public static bool pattern(string input,string regx)
    {
    
      if(input.Length==0 && regx.Length==0){
       return true;
      }
      
      if(input.Length>0 && regx.Length==0){
          return false;
      }
      
      
      if(input.Length==0 && regx.Length>0)
      {
          return true;
      }
      
       string curStr=input.Substring(0,1);
       string curReg=regx.Substring(0,1);
       string nextReg=regx.Substring(1,1);
      
    
      
      if(curStr==curReg)
      {
       return   pattern(input.Substring(1,input.Length-1),regx.Substring(1,regx.Length-1));
      }
      
      if(curReg=="*")
      {
          while(true)
          {
              if(curStr==nextReg && input.Length>0)
              {
                  input=input.Substring(1,input.Length-1);
                
              }
              else
              {
              if(regx.Length>2)    
                   regx=regx.Substring(2,2);
                  else
                  regx="";
        
              break;
              }
          }
          
          return   pattern(input,regx);
          
      }
      
      if(curReg=="+")
      {
          if(curStr==nextReg)
          {
              while(true)
              {
               if(curStr==nextReg  && input.Length>0)
               {
                input=input.Substring(1,input.Length-1);
               }
               else
               {
                    
                if(regx.Length>2)
                  regx=regx.Substring(2,2);
                else
                  regx="";
                  break;
               }
              }
              
              return   pattern(input,regx);
          }
          else
          return false;
      }
      
      return false;
        
    } 
}

/*

*********** USAGE *************
Pass the pattern you wish to match as a command line argument
Then enter the patterns you wish to match (one on each line)

The program will print the input string followed by a 1 or 0 indicating a match 
or mis match respectively.
Eg:
$./a.out a*b*c*abc
abc
abc:1
aabbcc
aabbcc:0

*/

#include <iostream>
#include <string>

using namespace std;

class matcher {
  string pattern;
  
  void compile();
  string candidates(int p, char& prev, int& inc);
  bool match_helper(string input, int p, int s, char& prev);

  public:
    matcher(string pattern) : pattern(pattern){
    }
    bool match(string input);
};

bool matcher::match(string input){
  int p = 0;
  int s = 0;
  char prev = '\0';
  return match_helper(input, p, s, prev);
}

bool matcher::match_helper(string str, int p, int s, char& prev) {
  if(p == pattern.length()) {
    return true;
  }
  string c;
  int inc = 0;
  c = candidates(p, prev, inc);
  for (int i = 0; i < c.length(); ++i) {
    if (str[s] == c[i]){
      if(!match_helper(str, p+inc, s+1, prev))
        continue;
      else
        return true;
    }
    if(c[i] == '\0'){
      prev = '\0';
      return match_helper(str, p+1, s, prev);
    } 
  }
  return false;
}

string matcher::candidates(int p, char& prev, int& inc) {
  string c;
  if(pattern[p] == '*' || pattern[p] == '+'){
    c += prev;
    c += '\0';
    inc = 0;
    return c;
  }
  else if(p+1 < pattern.length() && 
      (pattern[p+1] == '*' || pattern[p+1] == '+')) {
    c += pattern[p];
    prev = pattern[p];
    if(pattern[p+1] == '*'){
      c += '\0';
    }
    inc = 1;
    return c;
  }
  else {
    c += pattern[p];
    prev = '\0';
    inc = 1;
    return c;
  }
}


int main(int argc, char** argv){
  if(argc < 2){
    cout << "Please enter a pattern to match!" << endl;
    return 0;
  }

  matcher m(argv[1]);
  string input;
  while(true){
    cin >> input;
    cout << input << ":";
    cout << (m.match(input) ? "1" : "0") << endl;
  }
}

static class Solution{
		public static String str="";
		public static NDFA machine;
		public static void main(String[] args){
			boolean match = true;
			String input = "aab aab, aabab, aaaabbab";
			machine=CreateNDFA("aa*b*ab+");
			for(int i=0;i<input.length();i++){
				if(input.charAt(i)>='a' && input.charAt(i)<='z')
					str+=input.charAt(i);
				else{
					if(str.length()>0 && !DoesMatch(0, 0)){
						System.out.println("0");
						match = false;
						break;
					}
					str="";
				}
			}
			if(match)
				System.out.println(1);
		}
		
		public static NDFA CreateNDFA(String pattern){
			NDFA machine = new NDFA();
			for(int i=0;i<pattern.length();i++){
				if(i<pattern.length()-1){
					if(pattern.charAt(i+1)=='*'){
						char c = pattern.charAt(i);
						i++;
						if(i==pattern.length()-1)
							machine.Add(c, '1');
						else
							machine.Add(c, '0');
					}
					else if(pattern.charAt(i+1)=='+'){
						char c = pattern.charAt(i);
						i++;
						machine.Add('0', c);
						if(i==pattern.length()-1)
							machine.Add(c, '1');
						else
							machine.Add(c, '0');
					}
					else{
						if(machine.list.size()>0){
							if(machine.list.get(machine.list.size()-1).next=='0'){
								char preloop=machine.list.get(machine.list.size()-1).loop;
								machine.list.remove(machine.list.size()-1);
								machine.Add(preloop,pattern.charAt(i));		
							}
							else
								machine.Add('0',pattern.charAt(i));	
						}
						else
							machine.Add('0',pattern.charAt(i));	
					}
				}
				else{
					if(machine.list.get(machine.list.size()-1).next=='0'){
						char preloop=machine.list.get(machine.list.size()-1).loop;
						machine.list.remove(machine.list.size()-1);
						machine.Add(preloop,pattern.charAt(i));		
					}
					else
						machine.Add('0',pattern.charAt(i));			
					machine.Add('0','1');
				}
			}
			return machine;
		}
		
		public static class NDFA{
			public ArrayList<State> list = new ArrayList<State>();
			
			public void Add(char l, char n){
				list.add(new State(l,n));
			}
			
			public String ToString(){
				String result="";
				for(int i=0;i<list.size();i++){
//					result +="State:"+i+" loop:"+list.get(i).loop+" next:"+list.get(i).next+"\n";
						if (list.get(i).loop != '0')
							result += i + " --> "+ i + "  " + list.get(i).loop + "\n";
						if(list.get(i).next != '1')
							result += i + " --> "+ (i+1) + "  " + list.get(i).next + "\n";
				}
				return result;
			}

			class State{
				public char loop;
				public char next;
				
				State(char l, char n){
					loop = l;
					next = n;
				}
				
				boolean IsFinal(){
					if(next=='1')
						return true;
					return false;
				}
			}
		}
		
		public static boolean DoesMatch(int state,int charIndex){
			if(charIndex == str.length()){
				while(machine.list.get(state).next=='0')
					state++;
				if(machine.list.get(state).next=='1')
					return true;
				else
					return false;				
			}
			if(machine.list.get(state).loop == str.charAt(charIndex))
				if(DoesMatch(state,charIndex+1))
					return true;
			if(machine.list.get(state).next == str.charAt(charIndex))
				if(DoesMatch(state+1, charIndex+1))
					return true;
			if(machine.list.get(state).next == '0')
				if(DoesMatch(state+1, charIndex))
					return true;
			return false;
		}
	}

My code is working you can try ,I always welcome peoples who will find out sum issue :

/*
Pattern Matching 
---------------- 
Characters: a to z 
Operators: * + 
* -> matches zero or more (of the character that occurs previous to this operator) 
+ -> matches one or more (of the character that occurs previous to this operator) 

Output if a given pattern matches a string. 
Example: 
pattern:a*b 
string:aaab b, ab, aab, aaab, ab 
output:1 

pattern:a+aabc 
string:ab aabc, aaabc, aaaabc .. 
output:0 

pattern:aa*b*ab+ 
string:aab aab, aabab, aaaabbab 
output:1 

pattern: a+a*b* 
string: a ab, aab, aaabb 
output: 1 

Valid Assumptions: Please assume that both the pattern and string input are valid

*/
#include<iostream>
#include<string>
using namespace std;

typedef std::string::iterator i_string;
i_string temp;
bool Match( i_string re_start , i_string str_start , i_string re_end , i_string str_end ){
	if ( re_start != re_end || str_start != str_end ){
		if( *( re_start + 1 ) == *"*" ){
			if( *re_start == *str_start ){
				if ( Match(re_start + 2 , str_start , re_end  , str_end ) |
					      Match ( 	re_start , str_start + 1 , re_end , str_end ) |
					      Match( re_start + 2 , str_start + 1 , re_end , str_end ) ) return true ;
				else return false;
			}
			else 
				return ( Match (re_start + 2 , str_start  , re_end , str_end ) );
						}
		else if( * ( re_start + 1 ) == *"+" ){
			if ( *re_start == *str_start ){
				*(re_start + 1 )=*"*";
				return ( Match ( re_start , str_start + 1 , re_end , str_end ) );
			}
			else return false;
		}
		else if ( *re_start == *str_start ) return ( Match(re_start + 1 , str_start +1 , re_end , str_end ) );
		else return false;
	}
	else{
		if( re_start==re_end & str_start==str_end )
			return true;
		else return false;
	}
}

				



int main(){
	string s_re, s_string;
	std::cout<<"enter RE\n";
	std::cin>>s_re;
	std::cout<<"Enter string\n";
	std::cin>>s_string;
	i_string inm_re,inm_str,inm_re_end, inm_str_end;
	inm_re=s_re.begin();
	inm_str=s_string.begin();
	inm_re_end=s_re.end();
	inm_str_end=s_string.end();
	bool k=Match ( inm_re , inm_str  , inm_re_end , inm_str_end );
	k==false?std::cout<<"Not accepted\n":std::cout<<"Accepted\n";
       return 0;
}

Here is a simple code in C:

int regex(char* str, char* pattern)
{
	int str_marker=0;
	int pattern_marker=0;

	while(str[str_marker] && pattern[pattern_marker])
	{
		if(str[str_marker] == pattern[pattern_marker])
		{
			str_marker++;
			if(pattern[pattern_marker+1] == ‘+’)
				pattern[pattern_marker+1]=’*’;
			if(pattern[pattern_marker+1] != ’*’)
				pattern_marker++;
		}
		else if(pattern[pattern_marker+1]==’*’)
		{
			pattern_marker+=2;
		}
		else return 0;
	}

	return str[str_marker] == pattern[pattern_marker];
}

Did they really ask this question on a white board interview? The solution would be very time consuming.

I think we can use 2-order DP, here is my python code:

def mat(s, p):
    ps = []
    for c in p:
        if c != '*' and c != '+':
            ps.append(c)
        else:
            prev = ps[len(ps) - 1]
            ps.pop()
            ps.append(c + prev)

    m = len(ps)
    n = len(s)
    arr = [[False] * (n + 1) for i in xrange(m + 1)]

    # init
    arr[0][0] = True
    for i in xrange(m):
        if ps[i][0] == '*':
            arr[i + 1][0] = arr[i][0]

    # DP
    for i in xrange(m):
        for j in xrange(n):
            currs = s[j]
            tmp = False
            if ps[i][0] == '*':
                currp = ps[i][1]
                if currp == currs:
                    # use 0, 1, n times
                    tmp |= arr[i][j] | arr[i][j + 1] | arr[i + 1][j]
                else:
                    # can only use 0 time
                    tmp |= arr[i][j + 1]
            elif ps[i][0] == '+':
                currp = ps[i][1]
                if currp == currs:
                    # use 1, n times
                    tmp |= arr[i][j] | arr[i + 1][j]
            else:
                currp = ps[i]
                if currp == currs:
                    # must match
                    tmp |= arr[i][j]
            arr[i + 1][j + 1] = tmp

    return arr[m][n]

We can build a "Trie", where every edge will represent alphanumeric symbols from pattern.
'+' and '*' will result in a tree loops. After building a trie, we can traverse it recursively following every loop, until the whole string is matched.

var pattern = 'a+bc*',
string = 'bccc';

function test(pattern, string) {
    //build a trie
    var adjacencyList = {}, current = 0, cursor, length;

    for (cursor = 0, length = pattern.length; cursor < length; cursor++) {
        if (pattern[cursor + 1] === '*' && cursor < pattern.length - 1) {
            adjacencyList[current] = adjacencyList[current] || [];
            adjacencyList[current].push({
                node: current,
                edge: pattern[cursor]
            });
            //skip '*', because we have already processed it
            cursor++;
        } else {
            if (pattern[cursor] === '+') {
                adjacencyList[current] = adjacencyList[current] || [];
                adjacencyList[current].push({
                    node: current,
                    edge: pattern[cursor - 1]
                });
            } else {
                adjacencyList[current] = adjacencyList[current] || [];
                // alphanumeric
                adjacencyList[current].push({
                    node: ++current,
                    edge: pattern[cursor]
                });
            }
        }
    }

    //graph traverse
    function traverse(current, cursor) {
        if (cursor > pattern.length || pattern.length === 0) {
            return true;
        } else {
            return adjacencyList[current].some(function (adjacent) {
                if (adjacent.edge === string[cursor]) {
                    return traverse(adjacent.node, ++cursor);
                }
            });
        }
    }

    // start from graph root and first symbol of string
    return traverse(0, 0);
}

Simple recursive solution :

static bool PatternMatchString(string pattern, string s)
{
    return PatternMatchString(pattern, s, pattern.Length - 1, s.Length - 1);
}

static bool PatternMatchString(string pattern, string s, int i, int j)
{
    if (i < 0)
    {
        return j < 0;
    }
    
    bool result = false;
    
    if (char.IsLetter(pattern[i]))
    {
        result |= j >= 0 && pattern[i] == s[j] && PatternMatchString(pattern, s, i - 1, j - 1);
    }
    else
    {
        result |= pattern[i] == '+' && PatternMatchString(pattern, s, i - 1, j);
        result |= pattern[i] == '*' && PatternMatchString(pattern, s, i - 2, j);
        result |= j >= 0 && pattern[i - 1] == s[j] && PatternMatchString(pattern, s, i, j - 1);
    }
    
    return result;
}

This code will be ok.

bool IsMatch(const char * s, const char * p) {
  if (*s == '\0' && *p == '\0') return true;
  if (*p == '\0') return false;
  if (*(p + 1) == '*' && IsMatch(s, p + 2)) return true;
  
  if (*p == '+' || *p == '*') {
    if (IsMatch(s, p + 1)) return true;
    if (*s == *(s - 1) && IsMatch(s + 1, p)) return true;
    return false;
  } else if (*p == *s) {
    return IsMatch(s + 1, p + 1); 
  } else {
    return false;
  }
}

//s is input string, p is pattern
	public boolean isMatch(String s, String p){
		if(s == null || p == null){
			return s == null && p == null;
		}
		
		if(p.length() == 0){
			return s.length() == 0;
		}
		
	    if(p.length() == 1 || (p.charAt(1) != '*' && p.charAt(1) != '+')){
	        
	        if(s.length() == 0 || s.charAt(0) != p.charAt(0)){
	          return false;
	        }
	        return isMatch(s.substring(1), p.substring(1));
	      }else if(p.charAt(1) == '*'){
	        int index = -1;
	        
	        while(index < s.length() &&(index < 0 || s.charAt(index) == p.charAt(0))){
	          if(isMatch(s.substring(index+1), p.substring(2))){
	            return true;
	          }
	          index++;
	        }

	        return false;
	      }else{		
	    	  return isMatch(s, p.substring(2)) || isMatch(s.substring(1), p.substring(2));  
	      }

}

#include<stdio.h>
#include<string.h>
#include<stdlib.h>

int regex(char *pattern, char *string){
	//printf("--%s--, --%s--\n", pattern, string);
	if (*string == '\0' && *pattern == '\0'){
		return 1;
	}
	else if (*string == '\0' && *pattern != '\0'){
		if (*(pattern + 1) != '\0' && *(pattern + 1) == '*'){
			return 1;
		}
		else {
			return 0;
		}
		
	}
	
	if (*(pattern + 1) == '+'){
		if (*(string) != *(pattern)){
			return 0;
		}
		else{
			string++;
			while(*string == *pattern){
				string++;
			}
			pattern += 2;
		}
	}
	
	else if (*(pattern + 1) == '*'){
		if (*(string) != *(pattern)){
			pattern += 2;
		}
		else{	
			string++;
			while(*string == *pattern){
				string++;
			}
			pattern += 2;
		}	
	}
	
	else{
		if (*string != *pattern){
			return 0;
		}
		string++;
		pattern++;
	}
	
	return (1 & regex(pattern, string));

}

int main(){
	printf("%s %s %d 1\n", "a*b*", "aaa", regex("a*b*", "aaa"));
	printf("%s %s %d 1\n", "a*b*", "", regex("a*b*", ""));
	printf("%s %s %d 1\n", "a*b*c", "c", regex("a*b*c", "c"));
	printf("%s %s %d 1\n", "a*b", "aaaab", regex("a*b", "aaaab")); 
	printf("%s %s %d 0\n","a+bc*", "bccc", regex("a+bc*", "bccc")); 
	printf("%s %s %d 1\n", "ab+cd*", "abbcdd", regex("ab+cd*", "abbcdd"));
	printf("%s %s %d 1\n", "c*a*b", "aab" ,regex("c*a*b", "aab"));
	printf("%s %s %d 1\n", "a*b", "b", regex("a*b", "b")); 
	printf("%s %s %d 1\n", "a+a*b*", "ab", regex("a+a*b*", "ab")); 
	printf("%s %s %d 0\n", "aa*b*ab+", "aab", regex("aa*b*ab+", "aab")); 


}

bool isMatch(string pattern, string str){
			if(pattern.empty()) 
				return str.empty()?true:false;
			if(pattern[1]=='*'){
				while(pattern[0]==str[0]&&!str.empty()){
					if(isMatch(pattern.substr(2),str))
						return true;
					str=str.substr(1);
				}
				return isMatch(pattern.substr(2),str);
			}
			else if(pattern[1]=='+'){
				
					while(str.length()>0&&pattern[0]==str[0]){
						if(isMatch(pattern.substr(2),str.substr(1)))
							return true;
						str=str.substr(1);
					}
					return false;
				

			}
			else if(!str.empty()&&pattern[0]==str[0])
				return isMatch(pattern.substr(1),str.substr(1));
			else return false;
		}