剑指 Offer.19-正则表达式匹配

题目链接

问题描述

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

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/zheng-ze-biao-da-shi-pi-pei-lcof
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

官方解法(动态规划)

动态规划表格记录当前字母是否能够按照partten进行匹配，非常恶心的一道题

class Solution {
    public boolean isMatch(String s, String p) {
        int m = s.length() + 1, n = p.length() + 1;
        boolean[][] dp = new boolean[m][n];
        dp[0][0] = true;
         
        for(int j = 2;j < n;j += 2)
            // 当s为空时，p必须是a*b*的形式才能够正常进行匹配
            // 当s不为空，p为空是为false
            dp[0][j] = dp[0][j-2] && p.charAt(j-1) == '*';
        
        for(int i=1;i<m;i++){
            for(int j=1;j<n;j++){
                if(p.charAt(j-1) == '*'){
                    // 当目前字符不出现的情况下 能否匹配
                    if(dp[i][j-2]) dp[i][j] = true;
                    // 让字符多出现1次 能否匹配
                    else if(dp[i-1][j] && s.charAt(i-1) == p.charAt(j-2)) dp[i][j] = true;
                    // 当前一个元素为.时，当前可与任何符号通配
                    else if(dp[i-1][j] && p.charAt(j-2) == '.') dp[i][j] = true;
                }else{
                    // 在不是星号的时候，需要逐位进行匹配
                    if(dp[i-1][j-1] && s.charAt(i-1) == p.charAt(j-1)) dp[i][j] = true;
                    // 上一个成功匹配 且当前为单个字符通配符
                    else if(dp[i-1][j-1] && p.charAt(j-1) == '.') dp[i][j] = true;
                }
            }
        }
        // 返回字符串最后的匹配结果
        return dp[m-1][n-1];
    }    
}

本文采用署名-非商业性使用-相同方式共享 4.0 国际许可协议，转载请注明出处。