[LeetCode]10.Regular Expression Matching

题目

mplement regular expression matching with support for '.' and '*'.

'.' Matches any single character.
'*' Matches zero or more of the preceding element.

The matching should cover the entire input string (not partial).

The function prototype should be:
bool isMatch(const char *s, const char *p)

Some examples:
isMatch("aa","a") → false
isMatch("aa","aa") → true
isMatch("aaa","aa") → false
isMatch("aa", "a*") → true
isMatch("aa", ".*") → true
isMatch("ab", ".*") → true
isMatch("aab", "c*a*b") → true

思路

代码

/*------------------------------------------------------------------------------------
*   日期：2014-04-03
*   作者：SJF0115
*   题目: 10.Regular Expression Matching
*   来源：http://oj.leetcode.com/problems/regular-expression-matching/
*   结果：AC
*   来源：LeetCode
------------------------------------------------------------------------------------*/
#include <iostream>
#include <stdio.h>
#include <string.h>
using namespace std;

class Solution {
public:
    bool isMatch(const char *s, const char *p) {
        if(s == NULL || p == NULL || *p == '*') {
            return false;
        }
        if(*p == '\0') return *s == '\0';
        //next char is not '*': must match current character
        if(*(p+1) != '*') {
            if(*s == '\0') return false;
            if(*p != '.' && *p != *s) return false;
            return isMatch(s+1,p+1);
        }
        //next char is '*'
        else {
            int slen = strlen(s);
            if(isMatch(s,p+2)) return true;
            for(int i = 0; i < slen; ++i) {
                if(*p!='.' && *p != *(s+i)) return false;
                if(isMatch(s+i+1,p+2)) return true;
            }
            return false;
        }
    }
};

int main() {
    Solution solution;
    char* s = "abcbcd";
    char* p = "ab*bbc";
    bool result = solution.isMatch(s,p);
    cout<<result<<endl;
    return 0;
}

<script type="text/javascript"> $(function () { $('pre.prettyprint code').each(function () { var lines = $(this).text().split('\n').length; var $numbering = $('<ul/>').addClass('pre-numbering').hide(); $(this).addClass('has-numbering').parent().append($numbering); for (i = 1; i <= lines; i++) { $numbering.append($('<li/>').text(i)); }; $numbering.fadeIn(1700); }); }); </script>