题目描述

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

示例1

输入：
"aaa","a*a"
返回值：
true

解题思路

1. 动态规划 时间复杂度为O( ),空间复杂度为O( )

动态规划解题

1. 使用一个二维数组dp = new boolean[str.length() + 1][pattern.length() + 1]，长度+1是为了验证空串结果。
2. 外层寻魂表示str下标位移，内层循环表示pattern下标位移
3. 首先从空串开始验证
4. 如果pattern[j-1]为，就可以忽略符号前面的字符，直接撇撇

    public static boolean match(String str, String pattern) {
        // write code here
        // 多一行dp[0][0]是为了验证空串结果, dp[i][j]用来表示str前j个字符是否与pattern前[i]个字符匹配
        boolean[][] dp = new boolean[str.length() + 1][pattern.length() + 1];
        // 从0开始匹配因为要验证空串结果, 外层循环表示str字符下标
        for (int i = 0; i <= str.length(); i++) {
            // 内层循环表示pattern字符下标
          for (int j = 0; j <= pattern.length(); j++) {
              // j == 0并且 i == 0 同为true的情况标表示两个空串匹配
            if (j == 0) {
                dp[i][j] = (i == 0);
            } else {
                if (pattern.charAt(j - 1) == '*') {
                  // 当 j >= 2时, 当前位置前有一个或者多个字符的情况,， 直接可以忽略*号前面的字符，取j-2位置的值即可
                  if (j >= 2) {
                    dp[i][j] = dp[i][j - 2];
                  }
                  // 如果忽略*前面的字符, j-2位置的值为false时， 可以进行第二种情况判断, 即str[i-1] = patter[j-2]表示增值, 即*可以复制patter[j-2]位置的字符
                    // 当然如果patter[j-2] = '.'那么可以直接取 dp[i-1][j]处的值
                  // 下标多减1是因为dp是从1开始记录的
                    if ( !dp[i][j] &&  i >= 1 && j >= 2 && (str.charAt(i - 1) == pattern.charAt(j - 2) || pattern.charAt(j - 2) == '.')) {
                        // 使用或等于 两种情况有一种符合就行
                        dp[i][j] = dp[i - 1][j];
                    }
                } else {
                    // 如果字符不是*那么就很好判断了, 两个字符相等或者patter[j-1] = '.'都可以判断为相等
                  if (i > 0 && (str.charAt(i - 1) == pattern.charAt(j - 1) || pattern.charAt(j - 1) == '.')) {
                    // 取之前判断的结果即可
                    dp[i][j] = dp[i - 1][j - 1];
                  }
                }
            }
          }
        }
        return dp[str.length()][pattern.length()];
    }

举例

1. 拿 aaa, 与a.*a来做解答，可以得到下面这张图表示dp的值

   
   其中（0.0）位置为true表示"",""匹配成功，(1,1)位置为ture则表示"a","a"匹配成功，(1,3)位置为true则表示 "a"与"a.*"匹配成功，直到(3,4)得到最后的结果

2. 递归时间复杂度为O( ),空间复杂度为O(1)

递归思想相对于动态规划简单不少，推荐使用递归做法，先列出递归条件
1. 如果patter匹配到最后，str没有匹配完那么retrun false
2. 如果patter匹配到最后，str也匹配到最后，那么return true

    public boolean match (String str, String pattern) {
        // 判断str与pattern是否都匹配完成
        if (pattern.length() == 0) {
            return str.length() == 0;
        }
        // 如果当前str不为""并且 str[0]和pattern[0]相等，或者pattern[0]='.'那么都说明当前可以匹配
        boolean isMatch = (str.length() > 0 && (str.charAt(0) == pattern.charAt(0) || pattern.charAt(0) == '.'));
        //如果pattern当前长度大于1，并且当前字符为'*'那么可以无视当前str[1]的值直接进入到下一轮匹配
        if (pattern.length() > 1 && pattern.charAt(1) == '*') {
            // 截取字符串 分两种情况，
            // 第一种当前str与pattern[2]到pattern[patter.length()-1]匹配 ，这种情况下就表示*前面的字符出现了0次
            // 第二种 str[1]到str[str.length()-1]与pattern匹配。 这种情况下表示* 前面的字符出现了N次
            return match(str, pattern.substring(2)) || (isMatch && match(str.substring(1), pattern));
        }
        else {
            // 正常匹配
            return isMatch && match(str.substring(1), pattern.substring(1));
        }

    }