JZ19 正则表达式匹配

描述

请实现一个函数用来匹配包括'.'和'*'的正则表达式。

1.模式中的字符'.'表示任意一个字符

2.模式中的字符'*'表示它前面的字符可以出现任意次（包含0次）。

在本题中，匹配是指字符串的所有字符匹配整个模式。例如，字符串"aaa"与模式"a.a"和"ab*ac*a"匹配，但是与"aa.a"和"ab*a"均不匹配

数据范围:

1.str 只包含从 a-z 的小写字母。

2.pattern 只包含从 a-z 的小写字母以及字符 . 和 *，无连续的 '*'。

3. 0 \le str.length \le 26 \0≤str.length≤26 
4. 0 \le pattern.length \le 26 \0≤pattern.length≤26 

示例1

输入：

"aaa","a*a"

复制返回值：

true

复制说明：

中间的*可以出现任意次的a，所以可以出现1次a，能匹配上                

示例2

输入：

"aad","c*a*d"

复制返回值：

true

复制说明：

因为这里 c 为 0 个，a被重复一次， * 表示零个或多个a。因此可以匹配字符串 "aad"。                

示例3

输入：

"a",".*"

复制返回值：

true

复制说明：

".*" 表示可匹配零个或多个（'*'）任意字符（'.'）                

示例4

输入：

"aaab","a*a*a*c"

复制返回值：

false

代码

import java.util.*;
 
 
public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     *
     * @param str string字符串
     * @param pattern string字符串
     * @return bool布尔型
     */
    public boolean match (String str, String pattern) {
        // write code here
        System.out.println("xxx");
        int sLen = str.length();
        int pLen = pattern.length();
        char[] str_ = str.toCharArray();
        char[] pattern_ = pattern.toCharArray();
        boolean[][] dp = new boolean[sLen + 1][pLen + 1];
        boolean[] free = new boolean[pLen];
        System.out.println("xxx");
        for (int i = 0; i < sLen; i++) {
            if (i == 0 && (pattern_[0] == '.' || pattern_[0] == str_[0]))
                dp[i][0] = true;
            if (i >= 1)
                dp[i][0] = false;
        }//初始化j=0的列
        System.out.println("xxx");
        free[0] = false;
        for (int j = 1; j < pLen; j++) {
            if (j < 2 ){
              if(pattern_[j] == '*')
                free[j] = true;
                else
                free[j]=false;}
            else {
                if (free[j - 2] && pattern_[j] == '*')
                    free[j] = true;
                else
                    free[j] = false;
            }
        }
          System.out.println("xxx");
        for (int j = 1; j < pLen; j++) {
 
            if (pattern_[j] != '*') {
                dp[0][j] = free[j - 1] && (str_[0] == pattern_[j] || pattern_[j] == '.');
            } else {
                if (j - 2 >= 0)
                    dp[0][j] = dp[0][j - 2] || (free[j - 2] && (pattern_[j - 1] == str_[0] ||
                                                pattern_[j - 1] == '.'));
                else
                    dp[0][j] = pattern_[j - 1] == str_[0] || pattern_[j - 1] == '.';
            }
            //只要pattern里面有a*就行（全是*）
            //有一个不是*，这个是该字符
        }//初始化i=0的一列，只可能全是a*这种的,或者一开始有一个单个字符的
        System.out.println("xxx");
        for (int j = 1; j < pLen; j++) {
            for (int i = 1; i < sLen; i++) {
// System.out.println("yyy");
                //非常重要的异步就是对于*之前的元素不考虑他的值，因为也用不上，这样还可以少初始化一行
                if (j + 1 < pLen && pattern_[j + 1] == '*') {
                    continue;
                }
                if (pattern_[j] != '*') {
 
                    dp[i][j] = dp[i - 1][j - 1] && (pattern_[j] == str_[i] || pattern_[j] == '.');
                } else {
                    if (j - 2 < 0)
                        dp[i][j] = (dp[i - 1][j] && (pattern_[j - 1] == str_[i] ||
                                                     pattern_[j - 1] == '.'));
                    else
                        dp[i][j] = dp[i][j - 2] || (dp[i - 1][j] && (pattern_[j - 1] == str_[i] ||
                                                    pattern_[j - 1] == '.'));
                }
 
 
 
 
            }
        }
        System.out.println("xxx");
 
 
        return  dp[sLen - 1][pLen - 1];
    }
}

思路：

1.面对两个字符串的匹配问题的时候使用二阶的动态规划f(i,j)

2. 接下来的难点在于找到递推公式：

直接向很难明白

数学题的时候用过的这种思维：那就是特例，先把一些特殊情况解决。

要注意的是这个时候我们的问题已经变成了f(i,j)匹配的地推公式求解

那么分为三类，分别是p结尾为.,字母,*三种。

前两种很简单，直接拿出递推公式，最后一种比较难，还是不能够直接得出地推公式

怎么办呢，还是那句话，找特例

分类为匹配0次，一次，二次。。。。无穷多种（注意这里可以先写为无穷多）

接着另i=i-1找到递推公式，带入原本的式子，得到了简洁的地推公式

3. 最后一个难点，计算，因为计算必须有初始值才行，我们先初始化一些东西，但是这里又来一个问题，那就是i=0的时候很难初始化，这里我们又需要得出一个递推公式，先把这一行计算出来，然后在递推

4.一个小技巧，当下一个字符为*时不计算，因为那个时候用不到j-1的部分