leetcode力扣-10.正则表达式匹配解析【递归与动态规划】

女爷i 2022-11-03 11:49 92阅读 0赞

## 题目 ##

> 给你一个字符串 s 和一个字符规律 p，请你来实现一个支持 ‘.’ 和 ‘\*’ 的正则表达式匹配。  
> ‘.’ 匹配任意单个字符  
> ‘\*’ 匹配零个或多个前面的那一个元素  
> 所谓匹配，是要涵盖 整个 字符串 s的，而不是部分字符串。  
> `示例 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  
> `提示`：  
> 0 <= s.length <= 20  
> 0 <= p.length <= 30  
> s 可能为空，且只包含从 a-z 的小写字母。  
> p 可能为空，且只包含从 a-z 的小写字母，以及字符 . 和 \*。  
> 保证每次出现字符 \* 时，前面都匹配到有效的字符  
> \---------------  
> 来源：力扣（LeetCode）  
> 链接：https://leetcode-cn.com/problems/regular-expression-matching  
> 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

## 递归 ##

我们首先定义一个方法 `m(String s, String p)` 表示传入的字符串s与字符规律p是否匹配 ，返回 `boolean`

这道题目拿到手里，首先想到的就是递归。一步一步分析：

因为题目说了，s和p都是可能为空的，那么首先判断s和(或者)p为空的情况

说明：`s-1` ，`p-1` ，`p-2` 表示字符串截取掉末尾1位或者末尾2位

1.  如果 s 和 p 都为空，则返回 `true`
2.  如果 p 为空，则一定返回`false`，因为此时s不为空，始终无法匹配
3.  如果 s 为空，并且p以\*结尾（比如`.*`或者`x*`），m(s, p) = m(s, p-2) 此时相当于`.*`或者`x*`什么都没匹配，否则 m(s, p) = false

再考虑都不为空的情况：

![递归算法][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2Ftb3Njbg_size_16_color_FFFFFF_t_70_pic_center]  
还是需要简单说一下上面的方程是怎么得到的，对于s和p，如果存在s与p匹配的情况，那么

1.  匹配0次，去掉p的末尾字符
2.  匹配1次，去掉s的末尾字符 或者 同时去掉s/p的末尾字符（匹配1次就丢掉）

在p以`*`结尾时，为何没有同时去掉s/p的末尾字符呢？因为这个情况已经被包含了:

![结果被包含不在需要另外写][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2Ftb3Njbg_size_16_color_FFFFFF_t_70_pic_center 1]  
代码实现

class Solution { 
            public boolean isMatch(String s, String p) { 
                int sLen = s.length();
                int pLen = p.length();
    
                if (s.equals(p)) { 
                    return true;
                }
                if ("".equals(p)) { 
                    return false;
                }
                if ("".equals(s)) { 
                    if (p.endsWith("*")) { 
                        return isMatch(s, p.substring(0, p.length() - 2));
                    } else return false;
                }
                
                if (p.endsWith("*")) { 
                    if (p.charAt(pLen - 2) == '.') { 
                        // 1. p跟s匹配 去掉s末尾
                        return isMatch(s.substring(0, sLen - 1), p) ||
                                // 2. p跟s匹配 去掉p末尾
                                isMatch(s, p.substring(0, pLen - 2))
                                ;
                    } else if (p.charAt(pLen - 2) == s.charAt(sLen - 1)) { 
                        // 1. p跟s匹配 去掉s末尾
                        return isMatch(s.substring(0, sLen - 1), p) ||
                                // 2. p跟s匹配 去掉p末尾
                                isMatch(s, p.substring(0, pLen - 2))
                                ;
                    } else { 
                        // 3. p跟s不匹配 去掉p末尾
                        return isMatch(s, p.substring(0, pLen - 2));
                    }
                } else if (p.endsWith(".")) { 
                    // 4. 非*结尾匹配的情况 各自去掉末尾一位
                    return isMatch(s.substring(0, sLen - 1), p.substring(0, pLen - 1));
                } else { 
                    if (s.charAt(sLen - 1) == p.charAt(pLen - 1)) { 
                        // 4. 非*结尾匹配的情况 各自去掉末尾一位
                        return isMatch(s.substring(0, sLen - 1), p.substring(0, pLen - 1));
                    } else return false;
                }
            }
        }

## 动态规划 ##

动态规划三大特征

1.  `最优子结构` 最优子结构指的是，问题的最优解包含子问题的最优解。反过来说就是，我们可以通过子问题的最优解，推导出问题的最优解。后面阶段的状态可以通过前面阶段的状态推导出来。
2.  `无后效性` 无后效性有两层含义，第一层含义是，在推导后面阶段的状态的时候，我们只关心前面阶段的状态值，不关心这个状态是怎么一步一步推导出来的。第二层含义是，某阶段状态一旦确定，就不受之后阶段的决策影响。无后效性是一个非常“宽松”的要求。只要满足前面提到的动态规划问题模型，其实基本上都会满足无后效性。
3.  `重复子问题` 不同的决策序列，到达某个相同的阶段时，可能会产生重复的状态。

动态规划解题思路：

1.  `状态转移方程`：状态转移方程法有点类似递归的解题思路。我们需要分析，某个问题如何通过子问题来递归求解，也就是所谓的最优子结构。根据最优子结构，写出递归公式，也就是所谓的状态转移方程。有了状态转移方程，代码实现就非常简单了。一般情况下，我们有两种代码实现方法，一种是递归加“备忘录”，另一种是迭代递推。
2.  `状态转移表`：我们先画出一个状态表。状态表一般都是二维的，所以你可以把它想象成二维数组。其中，每个状态包含三个变量，行、列、数组值。我们根据决策的先后过程，从前往后，根据递推关系，分阶段填充状态表中的每个状态。最后，我们将这个递推填表的过程，翻译成代码，就是动态规划代码了。

本次解答过程，我们采用状态转移方程，因为方程比较好理解一些，而且画表格感觉有点麻烦。

我们需要定义一个二位数组存储s/p在不同索引位时，对应的匹配情况。比如`boolean mem[sLen+1][pLen+1]`，维数为何不跟s/p的长度一致呢？因为s/p都是可能为空的，所以多出来的长度1其实是为了表示`s/p为空`的情况。

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2Ftb3Njbg_size_16_color_FFFFFF_t_70_pic_center 2]  
把上述的过程总结一下：

1.  p以\*结果，a/b/c三种情况下：把`f(i, j) = f(i, j-2)`提取出来，然后再根据匹配的情况取 `|| f(i-1, j)` 的结果
2.  非\*结尾，s与p末尾匹配，`f(i,j) = f(i-1,j-1)`
3.  其他情况，无法匹配 `f(i,j) = false`;
4.  理解s与p的匹配过程，是从后往前推导，而二维数组的赋值过程是从前往后的，因为后面的状态是依赖前面计算出来的结果的；

代码实现

class Solution { 
       public boolean isMatch(String s, String p) { 
           int sLen = s.length();
           int pLen = p.length();
           // 定义一个二维数组 存放各自位字符s与正则p相互匹配的结果
           // 因为存在p或者(和)s为0的情况 所以二维数组的纬度比s/p的长度要多1
           boolean[][] mem = new boolean[sLen + 1][pLen + 1];
           // s和p都为0的情况 是可以匹配的
           mem[0][0] = true;
           // 有个问题需要注意
           // i/j并非是s/p的索引位 而需要减去1才是索引位
           for (int i = 0; i <= sLen; i++) { 
               // 为何不让j=0呢，因为j=0的时候 必定是无法匹配的
               for (int j = 1; j <= pLen; j++) { 
                   if (p.charAt(j - 1) == '*') { 
                       // 当 * 存在的时候 不论 * 前面的字符与s位字符是否匹配
                       // 计算方式的结果都是需要带上 如下表达式的 为什么呢 ？
                       // 假如1. *前面是.或者*前面的字符与s的字符匹配 那么
                       // mem[i][j] = mem[i - 1][j] || mem[i][j - 2] ;
                       // 假如2. *前面的字符与s的字符不匹配 那么
                       // mem[i][j] = mem[i][j - 2];
                       mem[i][j] = mem[i][j - 2];
                       
                       // 为何是j - 1呢 ？ 因为我需要判断的是 * 前面那一位 并且j - 1一定不会溢出(*前面一定有字符)
                       if (matches(s, p, i, j - 1)) { 
                           mem[i][j] = mem[i - 1][j] || mem[i][j];
                       }
                   } else if (matches(s, p, i, j)) { 
                       mem[i][j] = mem[i - 1][j - 1];
                   }
               }
           }
           return mem[sLen][pLen];
       }
    
       private boolean matches(String s, String p, int i, int j) { 
           if (i == 0) { 
               return false;
           }
           if (p.charAt(j - 1) == '.') { 
               return true;
           }
           return s.charAt(i - 1) == p.charAt(j - 1);
       }
    }

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2Ftb3Njbg_size_16_color_FFFFFF_t_70_pic_center]: /images/20221024/e8c09981c9c047e0b625faf42492374f.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2Ftb3Njbg_size_16_color_FFFFFF_t_70_pic_center 1]: /images/20221024/e06c01d2e9d54d45a28270bb0de3bacc.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2Ftb3Njbg_size_16_color_FFFFFF_t_70_pic_center 2]: /images/20221024/8f47741260314549a3ed86ef57907a3c.png