Why not using what you learn in compiler theory? The simple hand written recursive descent regex parser!


  • 0
    B

    For this problem, we only need to implement two 'productions' to hit the regular expression rules.

    These two rules are:

    1. symbol => [a-z]| '.'

    2. symbol* => epsilon | symbol symbol*

      bool isMatch(const char* s, const char* p);

      bool match_star(const char* s, const char* p) {
      return (isMatch(s, p+2) ||( (s[0] != '\0') && ( (s[0] == p[0]) || (p[0] == '.')) && match_star(s+1, p) ) );
      }

      bool isMatch(const char* s, const char* p) {
      if (s[0] == '\0' && p[0] == '\0') return true;
      if (p[1] == '*') {
      return match_star(s, p);
      }
      else {
      if (p[0] == '.') {
      return isMatch(s+1, p+1);
      }
      if ('a' <= p[0] && p[0] <= 'z') {
      return (s[0] == p[0]) && isMatch(s+1, p+1);
      }
      return false;
      }
      }


  • 0
    R

    It is an excellent idea but some test cases failed util I added some lines.

    #include <string>
    
    using namespace std;
    
    class Solution {
    private:
    	bool match_star(const char* s, const char* p) {
    		return (is_match(s, p + 2) || ((s[0] != '\0') && ((s[0] == p[0]) || (p[0] == '.')) && match_star(s + 1, p)));
    	}
    	bool is_match(const char* s, const char* p) {
    		//if (s[0] == '\0') return p[0] == '\0';
    		if (s[0] == '\0' && p[0] == '\0') return true;
    		if (p[1] == '*') {
    			return match_star(s, p);
    		}
    		else {
                       // maybe you forgot to check whether s is empty.
    			if (s[0] != '\0') {
    				if (p[0] == '.') {
    					return is_match(s + 1, p + 1);
    				}
    				else {
    					return (s[0] == p[0]) && is_match(s + 1, p + 1);
    				}
    			}
    			return false;
    		}
    	}
    public:
    	bool isMatch(string sStr, string pStr) {
    		const char* s = sStr.c_str();
    		const char* p = pStr.c_str();
    		return is_match(s, p);
    	}
    };
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.