（LeetCode）Java 求解正则表达式匹配

迷南。 2022-11-20 02:58 140阅读 0赞

### 文章目录 ###

*   *  一、题解
     *  二、代码
     *  三、总结

## 一、题解 ##

给你一个字符串 s 和一个字符串 p，请你来实现一个支持 `'.'` 和 `'*'` 的正则表达式匹配。

> `'.'` 匹配任意单个字符  
> `'*'` 匹配零个或多个前面的那一个元素

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L25hbmh1YWliZWlhbg_size_16_color_FFFFFF_t_70_pic_center]

--------------------

※※※※※※ 又是一道有关动态规划的题 ※※※※※※

思路和 [动态规划求解回文串][Link 1] 类似，但是这个题目的状态转移方程难多了。。。。

设置二维数组 `boolean[][] flag` ，`flag[i][j]` 表示字符串 s 前 i 个是否能够被字符串 p 前 j 个匹配

边界：空字符串表示可以匹配成功：`flag[0][0]=true`

状态转移方程：  
主要考虑 p\[j\] 的情况，它可以有字符，`.`，`*`三种取值情况。

第一种情况：如果`p[j] == s[i] || p[j]=='.'` 则 `flag[i][j] = flag[i-1][j-1]`，其中 `flag[i-1][j-1]` 表示前面的子串都匹配上了

第二种情况：`p[j]=='*'`,首先给了 `*`，明白 `*` 的含义是 匹配零个或多个前面的那一个元素，所以要考虑他前面的元素 `p[j-1]`。`*` 跟着它前一个字符走，前一个能匹配上 `s[i]`，`*` 才能有用，前一个都不能匹配上 `s[i]`，`*` 也无能为力，只能让前一个字符消失，也就是匹配 0 次前一个字符。  
所以按照 `p[j-1]` 和 `s[i]` 是否相等，我们分为两种情况：

*  `p[j-1] != s[i] ---> flag[i][j] = flag[i][j-2]`  
    这就是刚才说的那种前一个字符匹配不上的情况。  
    比如`(ab, abc * )`。遇到 `*` 往前看两个，发现前面 `s[i]` 的 `ab` 对 `p[j-2]` 的 `ab` 能匹配，虽然后面是 `c*`，但是可以看做匹配 0 次 `c`，相当于直接去掉 `c *`，所以也是 True。
 *  `p[j-1] == s[i] or p[j-1] == "."`  
    `*` 前面那个字符，能匹配 `s[i]`，或者 `*` 前面那个字符是万能的 `.`，因为 `.*` 就相当于 `..`，那就只要看前面可不可以匹配就行。  
    比如 `(##b , ###b*)`，或者 `( ##b , ###.* )` 只看 `###` 后面一定是能够匹配上的。  
    所以要看 `b` 和 `b*` 前面那部分 `##` 的地方匹不匹配。

如何判断前面是否匹配：

> `flag[i][j] = flag[i-1][j]` // 多个字符匹配的情况  
> `flag[i][j] = flag[i][j-1]` // 单个字符匹配的情况  
> `flag[i][j] = flag[i][j-2]` // 没有匹配的情况

看 `###` 匹不匹配，不是直接只看 `###` 匹不匹配，要综合后面的 `b*` 来分析  
这三种情况是 `or` 的关系，满足任意一种都可以匹配上，同时是最难以理解的地方：

`flag[i-1][j]` 就是看 s 里 b 多不多， `###` 和 `###b *` 是否匹配，一旦匹配，s 后面再添个 b 也不影响，因为有 `*` 在，也就是 `###b` 和 `###b*`也会匹配。

`flag[i][j-1]` 就是去掉 `*` 的那部分，`###b` 和 `###b` 是否匹配

`flag[i][j-2]` 就是 去掉多余的 `b*`，p 本身之前的能否匹配，`###b` 和 `###` 是否匹配，比如 `qqb` `qqbb*` 之前的 `qqb`, `qqb` 就可以匹配，那多了的 `b*` 也无所谓，因为 `b*` 可以是匹配 0 次 b，相当于 `b*` 可以直接去掉了。

三种满足一种就能匹配上。

## 二、代码 ##

public class Test { 
        public static void main(String[] args) { 
            String s = "aaa";
            String p = ".*";
            boolean result = isMatch(s, p);
            System.out.println(result);
        }
    
        private static boolean isMatch(String s, String p) { 
            int sLength = s.length();
            int pLength = p.length();
            //二维数组flag[i][j]表示s的前i个字符和p的前j个字符是否能够匹配
            //之所以长度加一，是因为这里flag[i][j],表示的前i个和前j个,再加个空字符串flag[0][0]，所以一共长度加一个
            boolean[][] flag = new boolean[sLength + 1][pLength + 1];
            //表示空字符串可以匹配
            flag[0][0] = true;
            //初始s空字符匹配的情况，也就是初始s 的空字符和 p 的第二个字符为 * 的情况
            for (int i = 1; i <= p.length(); i++) { 
                if (p.charAt(i - 1) == '*' && flag[0][i - 2]) { 
                    flag[0][i] = true;
                }
            }
            for (int i = 1; i <= sLength; i++) { 
                for (int j = 1; j <= pLength; j++) { 
                    //字符匹配
                    if (s.charAt(i - 1) == p.charAt(j - 1) || p.charAt(j - 1) == '.') { 
                        flag[i][j] = flag[i - 1][j - 1];
                        System.out.println("flag[" + i + "][" + j + "] = " + flag[i][j]);
                    } else if (p.charAt(j - 1) == '*') { 
                        //都不满足
                        if (s.charAt(i - 1) != p.charAt(j - 2) && p.charAt(j - 2) != '.') { 
                            flag[i][j] = flag[i][j - 2];
                            System.out.println("flag[" + i + "][" + j + "] = " + flag[i][j]);
                        } else { 
                            //满足三种情况中的一种
                            flag[i][j] = (flag[i-1][j] || flag[i][j - 1] || flag[i][j - 2]);
                            System.out.println("flag[" + i + "][" + j + "] = " + flag[i][j]);
                        }
                    }
                }
            }
            return flag[sLength][pLength];
        }
    }

要注意初始情况，`flag[0][]`,例如示例p中第二个字符就为`*`的情况

## 三、总结 ##

动态规划，关键就在于状态方程的确定。

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L25hbmh1YWliZWlhbg_size_16_color_FFFFFF_t_70_pic_center]: /images/20221120/8256cde25c2f45e79a5d3e4967e6b398.png
[Link 1]: https://blog.csdn.net/nanhuaibeian/article/details/109659081