AcWing 30. 正则表达式匹配 (剑指OFFER leetcode 10)

题目描述
请实现一个函数用来匹配包括’.’和’*’的正则表达式。

模式中的字符’.’表示任意一个字符，而’*’表示它前面的字符可以出现任意次（含0次）。

在本题中，匹配是指字符串的所有字符匹配整个模式。

例如，字符串”aaa”与模式”a.a”和”abaca”匹配，但是与”aa.a”和”ab*a”均不匹配。

样例

输入：

s="aa"

p="a*"

输出:true

算法1
很经典的题目也相当的难。
采用动态规划
dp[i][j] 表示 s[0~i)的字符串与p[0~j)的字符串是否匹配
那么有以下几个转换状态
1 p[j-1] 是字母而且与 s[i-1] 相等，那么当前dp[i][j]是否匹配就依赖于dp[i-1][j-1]
2 p[j-1] 是. 那么肯定与s[i-1]相等，当前dp[i][j]是否匹配就依赖于 dp[i-1][j-1]
情况1 2 类似可以在代码中一起判断
3 p[j-1] 是那么根据表示的前面字母的多次重复还是0次重复分为两种情况
3.1 如果是0次重复那么当前的p[j-1] == ‘*’ 和 p[j-2] 都可以忽略不计。那么 dp[i][j] = dp[i]j-2
3.2 如果是多次重复那么 p[j-2] 与s[i-1] 相等或者p[j-2]==’.’ 那么dp[i][j] = dp[i-1][j]

class Solution {

public:

    vector<vector<int>> dp;

bool isMatch(string s, string p) {

    int sn = s.size() ; int pn = p.size() ;

    dp = vector<vector<int>>(sn+, vector<int>(pn+, ));

    dp[][] = ;

    for (int i = ; i <= sn; i++) {

        for (int j = ; j <= pn; j++) {

            if (i >  && p[j - ] == '.' ) {

                dp[i][j] = dp[i - ][j - ];

            }

            else if (i >  &&  p[j - ] != '*'  && p[j-] == s[i-]) {

                dp[i][j] = dp[i - ][j - ];

            }

            else if (p[j - ] == '*') {

                //*

                if (j >  && dp[i][j - ] == )

                    dp[i][j] = ;

                else if (i >  && j >  && (p[j - ] == '.' || p[j - ] == s[i - ]) && dp[i - ][j] == )

                    dp[i][j] = ;

            }

        }

    }

    return dp[sn ][pn ];

}   

};

作者：defddr

链接：https://www.acwing.com/solution/acwing/content/3390/

来源：AcWing

著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

巴特西

AcWing 30. 正则表达式匹配 (剑指OFFER leetcode 10)

最新文章

热门文章