leetcode題解||Regular Expression Matching 問題

leetcode題解||Regular Expression Matching 問題

problem：

Implement 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

吐槽幾句：

字符串匹配，'.'和'*'的意義很簡單，不用陳述，但：

isMatch("aab", "c*a*b") → true

算哪門子事？

leetcode （http://articles.leetcode.com/2011/09/regular-expression-matching.html）已有好多人在爭論，這C*是不是可以代表0個C，我TM無語了。

最後的感覺就是這道題為了宣傳那個特定的算法而把條件改了？

PS： 看錯題目了.....2B了

（1）沒有*的情況很好解決，難在怎麼處理*

（2）比如ABBC與 A*C、A*BC，很清楚，利用深搜的思想，只要把BB與*、*B整體作匹配就OK了

自己寫了個測試程序，官方的那個扯淡條件通不過

#include 
#include 
using namespace std;
class Solution {
public:
    bool isMatch(const char *s, const char *p) {
        int n=0;
        int m=0;
        int index=0;
        while(*(s+n)!='\0')
        {
            n++;
        }
        while(*(p+m)!='\0')
        {
            m++;
        }
       // cout<<"n: "<
我測試了幾組，通過了，歡迎找BUG。