LeetCode刷题之旅（15）--正则表达式匹配（困难题）

每天属于自己的时间，就是慢慢的刷题的时候，啥也不用想，沉浸在写出最佳程序的过程中，沉浸在自己阅读大牛代码，提升自我的过程中，那种满足感，真的很让人享受<.>

题目:正则表达式匹配

给你一个字符串 s 和一个字符规律 p，请你来实现一个支持 '.' 和 '*' 的正则表达式匹配。

'.' 匹配任意单个字符
'*' 匹配零个或多个前面的那一个元素

所谓匹配，是要涵盖 整个 字符串 s的，而不是部分字符串。

说明:

s 可能为空，且只包含从 a-z 的小写字母。
p 可能为空，且只包含从 a-z 的小写字母，以及字符 . 和 *。
示例 1:

输入:
s = "aa"
p = "a"
输出: false
解释: "a" 无法匹配 "aa" 整个字符串。
示例 2:

输入:
s = "aa"
p = "a*"
输出: true
解释: 因为 '*' 代表可以匹配零个或多个前面的那一个元素, 在这里前面的元素就是 'a'。因此，字符串 "aa" 可被视为 'a' 重复了一次。
示例 3:

输入:
s = "ab"
p = ".*"
输出: true
解释: ".*" 表示可匹配零个或多个（'*'）任意字符（'.'）。
示例 4:

输入:
s = "aab"
p = "c*a*b"
输出: true
解释: 因为 '*' 表示零个或多个，这里 'c' 为 0 个, 'a' 被重复一次。因此可以匹配字符串 "aab"。
示例 5:

输入:
s = "mississippi"
p = "mis*is*p*."
输出: false

解题思路：

方法一：

递归解决方案：
在想到递归之前，我一直想用最简单的if else解决，在理清了思路以后，发现每次遇到p[j]=='*'时就进行不下去了，这时我意识到自己的思路还没有理清，所以推倒重来。然后发现，其实可以把思路精简为如下3种情况进行思考：
 1、当p[j]和s[i]都是字母的时候
    此时非常好分析，直接比较即可，如果匹配则j++，i++就可以了
 2、当p[j]='.'时
    直接跳过p[j]进行到下一个即可，类似情况1
 3、当p[j]='*'
    这是最麻烦的一种情况，但是*可以这么理解，它相当于对前一个字符的补充说明，说明前一个字符到底是0个还是多个,那么就可以视为*是和字母或者'.'是绑定在一起的，每当匹配字母或者''就检查后面是否跟着一个'*'。举个栗子，s:abbc和p:ab*c 当检查到第一个b的时候，发现p中的b后有一个*，此时只有两种可能，一是跳过p中的b*，b*的含义相当于有0个b，那么这时就会让s中的第一个b和p中的c匹配，如果不成功，那么就进行第二种情况，b*的含义就为多个b,那么s往后移动一位，p不变，再然后就是s中的b与p当前的b比较，然后重复上述过程跳过b*，s中的c就会与p中的c进行匹配,匹配成功结束. 
伪码如下：
bool isMatch(string s, string p) 
    {
        取p的第二个字符p[1],s的第一个字符s[0]
        if(p[1]=='*')
        {
            上述分析中的两种情况，1是p中的b*视为0个b，所以跳过；2是b*视为多个b，所以s往后移动一位
            return isMatch(s,p.substr(2))||(isMatch(s.substr(1),p));
        }
        else
        {
            当p[0]为普通字母或者'.'时，s和p直接后移一位即可
            return isMatch(s.substr(1),p.substr(1));
        }
    }
具体代码如下，基本就是将伪码就行完善

class Solution {
public:
    bool isMatch(string s, string p) 
    {
        if(p.size()<=0)return s.size()<=0;
        bool match=(s.size()>0&&(s[0]==p[0]||p[0]=='.'));
        if((p.size()>1)&&(p[1]=='*'))
        {
            return isMatch(s,p.substr(2))||(match&&isMatch(s.substr(1),p));
        }
        else
        {
            return match&&isMatch(s.substr(1),p.substr(1));
        }
    }
};
执行用时：548 ms

递归耗时严重，后续会增加其他方法，目前还在思考中。