Regular Expression Matching

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

思路是分别处理a*、.*、.、a的情况。

三周前写的lengthy code如下：

1 class Solution { 2 public: 3     bool isMatch(const char *s, const char *p) { 4         int sn = strlen(s); 5         int pn = strlen(p); 6         return recursive(s, sn, p, pn); 7     } 8      9     bool recursive(const char* s, int sn, const char* p, int pn) {10         if (sn == 0 && pn == 0) return true;11         if (pn == 0) return false;12         13         if (*(p + 1) != '\0') {14             if (*(p + 1) == '*') {15                 if (*p == '.') { // .*16                     int n = 0;17                     while (n <= sn) {18                         if (recursive(s + n, sn - n, p + 2, pn - 2)) return true;19                         n++;20                     }21                 } else { // a*22                     int n = 0;23                     while (n <= sn && *(s + n) == *p) {24                         if (recursive(s + n, sn - n, p + 2, pn - 2)) return true;25                         n++;26                     }27                     if (recursive(s + n, sn - n, p + 2, pn - 2)) return true;28                 }29             } else {30                 if (*p != '.' && *s != *p) return false;31                 if (recursive(s + 1, sn - 1, p + 1, pn - 1)) return true;32             }33         } else {34             if (*p != '.' && *s != *p) return false;35             if (recursive(s + 1, sn - 1, p + 1, pn - 1)) return true;36         }37     }38 };

今天看了Leetcode上1337的代码真是羞愧啊。

重写了一遍。思路还是一样。

1 class Solution { 2 public: 3     bool isMatch(const char *s, const char *p) { 4         if (*p == '\0') return (*s == '\0'); 5         // match single '\0', '.', 'a'... 6         if (*(p + 1) != '*') {  7             return ((*s == *p || (*p == '.' && *s != '\0')) && isMatch(s + 1, p + 1)); 8         } 9         10         // match a*, .*11         while ((*s == *p || (*p == '.' && *s != '\0'))) {12             if (isMatch(s++, p + 2)) return true;13         }14         15         // ignore a*， *p != '.' && *s != *p16         return isMatch(s, p + 2);17     }18 };