【JAVA、C++】LeetCode 010 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”，“aa”，“aaa”……这一点比较容易让人犯迷糊
二、必须完全比配，即isMatch("aa","aaa") → false
三、第一个参数String s 是不含有“.”和“*”，因此不要把程序复杂化
Java实现如下：

static public boolean isMatch(String s, String p) {
        // 如果从s长度入手，s.length() == 0时（"","a*")、("","a*b*")都会返回true
        if (p.length() == 0)
            return s.length() == 0;
        else if (p.length() == 1)
            return s.length() == 1&& (p.charAt(0) == '.' || s.charAt(0) == p.charAt(0));
        if (p.charAt(1) != '*') {
            if (s.length() == 0|| (p.charAt(0) != '.' && s.charAt(0) != p.charAt(0)))
                return false;
            return isMatch(s.substring(1), p.substring(1));
        } 
        else if (isMatch(s, p.substring(2)))
                return true;
        else {
                int i = 0;
                while (i < s.length()&& (p.charAt(0) == '.' || p.charAt(0) == s.charAt(i))) {
                    if (isMatch(s.substring(i + 1), p.substring(2)))
                        return true;
                    i++;
                }
            }
            return false;
    }

C++面向对象：

 1 class Solution {
 2 public:
 3     bool isMatch(string s, string p) {
 4         if (p.length() == 0)
 5             return s.length() == 0;
 6         else if (p.length() == 1)
 7             return s.length() == 1 && (p[0] == '.' || s[0] == p[0]);
 8         if (p[1] != '*') {
 9             if (s.length() == 0 || (p[0] != '.' && s[0] != p[0]))
10                 return false;
11             return isMatch(s.substr(1), p.substr(1));
12         }
13         else if (isMatch(s, p.substr(2)))
14             return true;
15         else {
16             int i = 0;
17             while (i < s.length() && (p[0] == '.' || p[0] == s[i])) {
18                 if (isMatch(s.substr(i + 1), p.substr(2)))
19                     return true;
20                 i++;
21             }
22         }
23         return false;
24     }
25 };

C++ 面向过程（效率高）：

 1 class Solution {
 2 public:
 3 bool isMatch(const char *s, const char *p) {  
 4         if (!p[0])  
 5             return !s[0]; 
 6         if (!p[1] || p[1] != '*')  
 7             return s[0] && (p[0] == '.' || s[0] == p[0])&& isMatch(++s, ++p);  
 8         while (s[0] && (p[0] == '.' || s[0] == p[0]))  
 9             if (isMatch(s++, p + 2))  
10                 return true;  
11         return isMatch(s, p + 2);  
12     }  
13     bool isMatch(string s, string p) {
14         return isMatch(s.data(), p.data());
15     }
16 };