剑指offer—正则表达式匹配 解答

剑指offer—正则表达式匹配

题目描述

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

思路

动态规划

因为*符号可以代替一个或者多个字符,所以我们用一般循环是很难解出来的,当然递归可以做出来,但是递归花费了多次重复的计算,我们选取动态规划来构建最优子问题解决

首先我们考虑一下动态规划的最优子问题是什么?还有状态怎么转移?

  • 最优子问题

原字符数组str的i个元素能否匹配pattern数组的j个元素,我们选取的是自顶向下的方法,一会你就知道为什么要这样做了

所以最优子问题就是str从i到最后的字符数组能否匹配pattern从j到最后的字符数组,即str[i:]->pattern[j:]

找到最优子问题后我们看一下状态如何进行转移?

当前字符总的可以分为三种情况:1.正常字符2.*符号3..符号

当遇到正常字符的时候,我们只需比较两个数组该位是否相等,相等就继续比较下一个;

当遇到.符号时,我们无需判断是否相等,只需要继续比较下一个即可;

当遇到*符号时,较为复杂,它可能让前面一个字符取0个或者多个

我们在循环计算每个dp位置值的时候,就可以分为以下几种情况:

  1. 把遇到正常字符和遇到.字符情况合并,如果该位字符相等或者是.字符并且dp[i+1][j+1]为true的话就为true,不然就为false

  2. 另外一种情况就是遇到下一个字符*字符

    1. 匹配前面0个字符就是i不动,j往后移动两位跳过这个*,这就是为什么要使用从顶向下,从右向左移动的方法的原因,我们需要首先计算出右边的的值,才能向右移动获取到右边的dp值
    2. 匹配多个字符是str数组每往右一位对应一个字符,pattern数组不变,保持使用*去匹配下一个字符,所以我们每个dp值只需要i往后移动一位,j不移动,继续使用*号

    这两种情况取或,满足取0位或者当前字符匹配并且取一位时设置为true

  3. 两种情况公共部分:都需要判断当前位是否匹配

边界值

在最右边进行移位是会越界的,我们需要通过条件语句i<str.length也就是原始数组str位置不能超过左右边,j<p.length-1也就是匹配数组pattern不能达到倒数第一个元素来控制可以拿到右移两位的dp值

要把最右边值设置为true,都为空时匹配成功

代码

public class Solution {
    public boolean match(char[] s, char[] p){
        boolean [][] dp = new boolean[s.length+1][p.length+1];
        dp[s.length][p.length] = true;
        for(int i=s.length;i>=0;i--){
            for(int j=p.length-1;j>=0;j--){
                boolean firstMatch = i<s.length&&(s[i]==p[j]||p[j]=='.');
                if(j<p.length-1&&p[j+1]=='*')
                    dp[i][j] = dp[i][j+2]||firstMatch&&dp[i+1][j];
                else
                    dp[i][j] = firstMatch&&dp[i+1][j+1];
            }
        }
        return dp[0][0];
    }
}
  • 本文作者: dzou | 微信:17856530567
  • 本文链接: http://www.dzou.top/post/regex-match.html
  • 版权声明: 本博客所有文章除特别声明外,均采用 CC BY-NC-SA 4.0 许可协议。转载请注明出处!
  • 并保留本声明和上方二维码。感谢您的阅读和支持!