String S could also be a regular expression


  • 0
    J

    The problem did not indicate that string s cannot be a regular expression.

    For example, isMatch("bbbb*a", "b*a") should return true instead of false. Maybe the OJ should build test cases for these as well? Here is my solution, I think it handled the case.

    class Solution {
    public:
        bool isStar(string s) {
          if(s.length() > 1 && s[1] == '*')
            return true;
          return false;
        }
        
        bool charMatch(char a, char b) {
          if(a == '.' || b == '.' || a == b)
            return true;
          return false;
        }
        
        bool isMatch(string s, string p) {
          if(isStar(s) && !isStar(p)) return isMatch(p, s);
          int m = s.length(), n = p.length();
          if(m == 0 && n == 0) return true;
          if((m == 0 && !isStar(p)) || (n == 0 && !isStar(s))) return false;
        
          if(!isStar(p)) {
            if(charMatch(s[0], p[0]))
              return isMatch(s.substr(1, m - 1), p.substr(1, n - 1));
            else
              return false;
          }
        
          int i = 0;
          do {
            if(isMatch(s.substr(i, m - i), p.substr(2, n - 2)))
              return true;
            i++;
          } while(i - 1 < m && charMatch(s[i-1], p[0]));
        
          return false;
        }
    };

  • 0
    B

    since * is a special character for specifying patterns, if you need to match * in s like "bbbb*a", you should specify p as "b**a"


  • 0
    B

    since * is a special character for specifying patterns, if you need to match * in s like "bbbba", you should specify p as "b*a"


Log in to reply
 

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