Leetcode_10_正则表达式匹配

07 Jun 2019 | Algorithm |

这道题来自于Leetcode的第10题

题目描述：

给你一个字符串 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

方法一：递归回溯

首先，需要考虑匹配符号 * , 它会影响前面的字符，根据不同状态有：

如果 p[j+1] == ‘*’:
- 则有当前字符出现0次，match(s[i],p[j+2]);
- 当前字符出现1次，match(s[i+1],p[j+2]);
- 当前字符出现多次，match(s[i],p[j+1]);
如果 p[j+1] != ‘*’:
- 那么根据当前字符处理下一个，有 match(s[i],p[j+1])。

如果觉得文字描述的不太准确的，就直接看代码吧。

递归代码：

     /**
     * 递归
     *
     * @param s 字符串
     * @param p 模式串
     * @return 返回结果是否匹配
     */
 public boolean isMatch(String s, String p) {
        if (s == null || p == null)
            return false;
        s = s.trim();
        p = p.trim();

        return match(s, p, 0, 0);
    }

    private boolean match(String s, String p, int sIndex, int pIndex) {
        // 匹配成功
        if (sIndex == s.length() && pIndex == p.length())
            return true;
        //字符串还没匹配完，模式串就完了，匹配失败
        if (sIndex != s.length() && pIndex == p.length())
            return false;

        //前面出现 通配符 '*'
        if (pIndex < p.length() - 1 && p.charAt(pIndex + 1) == '*') {
            if ((sIndex != s.length() && s.charAt(sIndex) == p.charAt(pIndex)) || (sIndex != s.length() && p.charAt(pIndex) == '.')) {
                return match(s, p, sIndex, pIndex + 2)  //'*'零次，比如：ab,a*ab
                        || match(s, p, sIndex + 1, pIndex + 2)  //'*'一次，比如：abc,a*bc
                        || match(s, p, sIndex + 1, pIndex);   //'*'多次，比如：aaaa,a*
            } else {
                return match(s, p, sIndex, pIndex + 2); //当前不匹配，  比如：aa,c*aa
            }
        }

        //处理 前面没有通配符 '*'
        if ((sIndex != s.length() && s.charAt(sIndex) == p.charAt(pIndex)) || (sIndex != s.length() && p.charAt(pIndex) == '.')) {
            return match(s, p, sIndex + 1, pIndex + 1);
        }

        return false;

    }

方法二：动态规划

用递归实现，一般都可以转成动态规划来消除递归过程中重复计算的子问题。动态规划最重要的是写出转移方程，这里，直接给出结果：

如果 p[j+1] == ‘*’
dp[i][j] = dp[i][j+2] || dp[i+1][j] && curMatch 
(dp是状态转移表，curMatch表示当前字符是否匹配)

如果 p[j+1] != ‘*’
dp[i][j] = dp[i+1][j+1] && curMatch 

这个转移方程肯定不是一下就直接看出来的，需要根据例子去不断尝试，才能找出这种规律。

因为*会影响前面的字符，我们在从左往右计算时总是要考虑后面的字符（考虑后面是不是有*），但是后面还没有计算，还不知道结果。

所以，我们就从后往前算，这样方便一点，因为后面此时已经计算出来了（前面写的转移方程也是从后往前的）。当然，动态规划可以从左到右，也可以从右到左。

现在考虑

s[i:]表示字符串s从i(包括i)到末尾的子串； p[j:]表示模式串p从j (包括j)到末尾的子串；在状态表中dp[i][j] 表示s[i:]和p[j:]是否匹配。

动态转移方程

动态转移方程举例说明：

` p[j+1] != ‘*’`

` p[j+1] == ‘*’`

计算状态转移表

当前实例：
字符串s："aab"
模式串p："c*a*b"

多加的一列和一行是为了方便计算，因为最后字符有+1(i+1或者j+1)的操作，可能越界。

当前实例：
字符串s："aab"
模式串p："c*a*b"

上面的实例图可以很清楚看到动态转移的过程，我们是从后往前进行计算的，所以是从第3、2、1、0行。

最后，再拿表中的例子说明一下。当i=1, j=2时,状态表情况如下：

当前实例：
字符串s："aab"
模式串p："c*a*b"

动态规划代码

 /**
     * 动态规划
     *
     * @param s 字符串
     * @param p 模式串
     * @return 返回结果是否匹配
     */
    public boolean isMatch(String s, String p) {
        //参数检查
        if (s == null || p == null)
            return false;
        //动态规划状态转移表
        boolean[][] dp = new boolean[s.length() + 1][p.length() + 1];

        //最后一个为true
        dp[s.length()][p.length()] = true;

        //初始化最后一行
        for (int j = p.length() - 1; j >= 0; --j) {
            if (j + 1 < p.length() && p.charAt(j + 1) == '*') {
                dp[s.length()][j] = dp[s.length()][j + 2];
            }//else  其他情况为false，省略了
        }

        //初始化最后一列,  但都为false，省略了

        //计算状态转移表
        for (int i = s.length() - 1; i >= 0; --i) {

            for (int j = p.length() - 1; j >= 0; --j) {
                boolean curMatch = s.charAt(i) == p.charAt(j) || p.charAt(j) == '.';
                //对匹配符号的处理
                if (j + 1 < p.length() && p.charAt(j + 1) == '*') {
                    dp[i][j] = dp[i][j + 2] || dp[i + 1][j] && curMatch;
                } else {
                    dp[i][j] = dp[i + 1][j + 1] && curMatch;
                }
            }
        }

        //返回结果
        return dp[0][0];
    }

在状态转移表中，每次只会使用相邻的两行，所以可以使用滚动数组来节约空间。

/**
     * 动态规划: 使用滚动数组节约空间
     *
     * @param s 字符串
     * @param p 模式串
     * @return 返回结果是否匹配
     */
    public boolean isMatch(String s, String p) {
        //参数检查
        if (s == null || p == null)
            return false;
        //动态规划状态转移表
        boolean[][] dp = new boolean[2][p.length() + 1];

        //计算状态转移表
        for (int i = s.length(); i >= 0; --i) {
            for (int j = p.length(); j >= 0; --j) {

                if (j == p.length()) {
                    dp[i % 2][j] = i == s.length();
                }else {

                    boolean curMatch = i < s.length() && (s.charAt(i) == p.charAt(j) || p.charAt(j) == '.');

                    if (j + 1 < p.length() && p.charAt(j + 1) == '*') {
                        dp[i % 2][j] = dp[i % 2][j + 2] || curMatch && dp[(i + 1) % 2][j];
                    } else {
                        dp[i % 2][j] = curMatch && dp[(i + 1) % 2][j + 1];
                    }

                }

            }

        }

        return dp[0][0];
    }

Midnight