LeetCode 第 10 题：正则表达式匹配

方法一：递归，减而治之

Java 代码：

/**
 * @author liweiwei1419
 * @date 2019/9/23 1:12 下午
 */
public class Solution4 {

    // 递归

    public boolean isMatch(String s, String p) {
        if (p.isEmpty()) {
            return s.isEmpty();
        }
        boolean firstMatch = !s.isEmpty() && (s.charAt(0) == p.charAt(0) || p.charAt(0) == '.');
        if (p.length() > 1 && p.charAt(1) == '*') {
            // '*' 表示 0 次
            if (isMatch(s, p.substring(2))) {
                return true;
            }
            return firstMatch && isMatch(s.substring(1), p);
        }
        return firstMatch && isMatch(s.substring(1), p.substring(1));
    }
}

Python 代码：

class Solution:
    def isMatch(self, s: str, p: str) -> bool:
        if len(p) == 0:
            return len(s) == 0
        first_match = len(s) > 0 and (s[0] == p[0] or p[0] == '.')

        if len(p) > 1 and p[1] == '*':
            if self.isMatch(s, p[2:]):
                return True
            return first_match and self.isMatch(s[1:], p)
        return first_match and self.isMatch(s[1:], p[1:])

C++ 代码：

#include <iostream>
#include <string>

using namespace std;

class Solution {
public:
    bool isMatch(string s, string p) {
        if (p.empty()) {
            return s.empty();
        }
        bool firstMacth = !s.empty() && (s[0] == p[0] || p[0] == '.');
        if (p.size() > 1 && p[1] == '*') {
            if (isMatch(s, p.substr(2))) {
                return true;
            }
            return firstMacth && isMatch(s.substr(1), p);
        }
        return firstMacth && isMatch(s.substr(1), p.substr(1));
    }
};