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。