How to solve Leetcode 10: Regular Expression Matching problem efficiently?

本文共计578个文字，预计阅读时间需要3分钟。

该题目的意思是，给定一个字符串s和一个模式字符串p，判断这两个字符串是否匹配。特殊的是，p字符串中可能包含字符'.'和'*'。'.'可以代表任意字符，而'*'可以代表任意长度的字符（包括0个字符）。判断思路如下：

这道题的题意是，给出一个字符串s和匹配串P。判断两个串是否匹配。特殊的是p串中会有. 和 *。.表示可以代替任意字符，*则是可以重复前面的字符任意次（0次也可以）
大体上思路就是，对于p的一个*，比如说是a*，我们要搞明白这在s串中对应了究竟几个a。然后我们需要把匹配上的字符在原本的字符串中划掉，再跑身下的字符串，也就是递归。
这个思路是以*为基础。把*和前面一个字符在p中当作一个整体，看匹配的s中多少个对应前面的字符。

考虑到递归，就要考虑最终情况。
如果p为空，则S为空则true，s不为空则false。
如果p长度为1，那么只有s长度为1且和p这一位相同才返回true，否则false。
如果p长度不是1，那么分两种情况：
第一种，当前两位不是一个字符+*，那么就比较s和p最前面一位，如果一样就递归s、p个删去最前面一位的，不一样返回false。