LeetCode 10：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

居然是实现正则表达式字符串匹配，但是好像只有全匹配和带*的模式匹配

一开始题目理解错了，以为p是pattern，和正常模式匹配一样只要s中有这个pattern即可，但是要求里有这么一条：

The matching should cover the entire input string (not partial).

也就是说这个pattern必须覆盖匹配掉整个字符串s

比如直接通过python的re模块完成

class Solution(object):
    def isMatch(self, s, p):
        """
        :type s: str
        :type p: str
        :rtype: bool
        """
        import re
        pattern = '^%s$' % p
        return re.search(pattern, s) is not None

只需要保证字符串的开头和结尾，提交是正确的

假如要分支结构考虑所有情况，结合递归，可真麻烦

摘自简书一哥们的实现的过程，讲述的比较详细

https://www.jianshu.com/p/85f3e5a9fcda

Java实现源码也来自上面链接

package com.maoxiaomeng;

/**
 * @author lihui
 * @date 2018/3/26 12:31
 */

class Solution {
    public boolean isMatch(String s, String p) {
        if (p.isEmpty()) {
            return s.isEmpty();
        }
        if (p.length() == 1 || p.charAt(1) != '*') {
            if (s.isEmpty() || (p.charAt(0) != '.' && p.charAt(0) != s.charAt(0))) {
                return false;
            } else {
                return isMatch(s.substring(1), p.substring(1));
            }
        }
        while (!s.isEmpty() && (s.charAt(0) == p.charAt(0) || p.charAt(0) == '.')) {
            if (isMatch(s, p.substring(2))) {
                return true;
            }
            s = s.substring(1);
        }
        return isMatch(s, p.substring(2));
    }
}

细细体会一下