LeetCode题目：正则表达式匹配

题目描述：

请实现一个函数用来匹配包含’. '和 '’(这里是星号) 的正则表达式。模式中的字符’.‘表示任意一个字符，而’'表示它前面的字符可以出现任意次（含0次）。在本题中，匹配是指字符串的所有字符匹配整个模式。例如，字符串"aaa"与模式"a.a"和"abaca"匹配，但与"aa.a"和"ab*a"均不匹配。

示例 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 = “cab”

输出: true

解释: 因为 ‘*’ 表示零个或多个，这里 ‘c’ 为 0 个, ‘a’ 被重复一次。因此可以匹配字符串 “aab”。

示例 5:

输入:

s = “mississippi”

p = “misisp*.”

输出: false

s 可能为空，且只包含从 a-z 的小写字母。

p 可能为空，且只包含从 a-z 的小写字母以及字符 . 和 ，无连续的 '’。

来源：力扣（LeetCode）

链接：https://leetcode-cn.com/problems/zheng-ze-biao-da-shi-pi-pei-lcof

著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

解题思路：

首先需要想到，这道题里面pattern和text前面对的上不一定后面对的上，必须要全部对的上了才能返回true，所以说，前面的内容匹配完了之后要开启后面内容的匹配，自然而然应该想到用递归思想，如果用循环来做，情况就会很复杂。

首先，递归的结束条件是输入这次递归算法的pattern已经空了，这是需要text也是空的才能返回true，否则，text还有内容还没匹配完，肯定是false。

递归算法的内容：

第一个要做的是，在text还没空的情况下，看这次递归输入的pattern和text的首字母是不是匹配，这里要注意 ‘.’ 的情况，如果匹配了就得到first_match为true，否则first_match为false，这个是这次递归返回的判断条件之一，先放着。

第二个需要判断，这次递归输入的pattern的长度是否大于2，并且pattern的第二个字符是不是星号，如果条件成立，这里又要分两种情况：

第一种情况，不管first_match是否为true（可以理解为false，这样星号就表示出现0次 ），如果text和pattern自第三个字符开始的子串匹配，就返回true。

第二种情况，在first_match为true的情况下，text自第二个字符开始的子串应该和pattern能匹配成功（细细琢磨，星号能表示前面的符号出现任意次，这样每次开启一个递归方法，text的输入少了当前first_match位true的字符，直至first_match不成功，就出现了被星号修饰的字符出现0次的情况，这样就回到了第一种情况），则返回true。

第三步，就是第二步条件不成立的情况：pattern的长度小于2，或者pattern的第二个字符不是星号，这样就需要first_match为true，并且text自第二个字符的子串和pattern自第二个字符的子串能够匹配得上，这样就返回true。

代码（Java）：

public class Solution {
	public static void main(String[] args) {
		String text = "aab";
		String pattern = "c*a*b";
		System.out.println(isMatch(text, pattern));
	}
	
    public static boolean isMatch(String text, String pattern) {
        if (pattern.isEmpty()) return text.isEmpty();  //如果样式是空的，那么字符串是空的就返回真，否则返回假
        boolean first_match = (!text.isEmpty() &&	//样式不是空的情况下，字符串不能为空
                               (pattern.charAt(0) == text.charAt(0) || pattern.charAt(0) == '.'));
        											//表示第一个字符是不是对上了  这个是最终返回的判断条件之一，先放在这里
        if (pattern.length() >= 2 && pattern.charAt(1) == '*'){  //样式的长度大于2，而且第二个字符是*
            return (isMatch(text, pattern.substring(2)) || //用上了递归     text和pattern第3个后的内容是不是匹配上了
                    (first_match && isMatch(text.substring(1), pattern)));  //或者第1个字符对上了而且text第2个字符起后面的内容和pattern对上了
        } else {  //如果pattern的长度小于2或者pattern的第二个字符不是*
            return first_match && isMatch(text.substring(1), pattern.substring(1));  //第一个字符对上了，text和pattern第二个后面的内容匹配上了
        }
    }
}