数据结构学习 jz19正则表达式匹配

发布时间:2024年01月03日

关键词:动态规划

这题确认dp状态不难,最关键也是最麻烦的是找到正确的转移方程。我参考了这位大神的答案

题目:

思路:

dp状态:

dp[i][j]?:代表字符串?s?的前?i?个字符和?p?的前?j?个字符能否匹配。(注意这里dp的第0行和第0列表示s为空和p为空的情况)

初始状态:

dp[0][0]=1 因为空字符串和空字符串可以匹配

如下表格所示

‘’.*a
‘’1000
b0000
c0000
a0000

转移方程:

假如我们需要确认dp[i][j]的情况。

需要分成两种大的情况:

1、如果p[j-1]不等于*:

????????(即p字符串当前检测的字符,-1是因为dp方程里面我们多开了一行)

????????那么就看p[j-1]是否等于s[i-1] 或?p[j-1]是否等于'.':如果是,则dp[i][j]和dp[i-1][j-1]状态一致(多加了一组匹配字符);如果不是,则保持0。

????????比如:

????????p[j-1]等于'.':dp[i][j]和dp[i-1][j-1]状态一致

‘’.*a
‘’1010
b0100
c0000
a0000

?????????p[j-1]等于'.':dp[i][j]和dp[i-1][j-1]状态一致

‘’.*a
‘’1010
b0110
c0000
a0000

?????????p[j-1]等于s[i-1]:dp[i][j]和dp[i-1][j-1]状态一致

‘’.*a
‘’1010
b0110
c0010
a0011

这一步的具体代码:

if (i > 0 && j > 0 && (s[i - 1] == p[j - 1] || p[j - 1] == '.'))//不是*
                {
                    dp[i][j] = dp[i - 1][j - 1];
                }

2、如果p[j-1]等于*:

? ? ? ? 这个时候需要把*和前面的字符c看作一个整体,一起讨论,因为*的内容得取决于c。

? ? ? ? 那么还得分两种情况,这两种情况得取 或

? ? ? ? (1)看c*:这个时候匹配一个及以上的前面的那一个元素。

????????????????这个时候得看p[j-2]是否等于s[i-1] 或?p[j-2]是否等于'.':如果是,则dp[i][j]和dp[i-1][j]状态一致(相当于s后移,p不用动,因为*可以充当多个c);如果不是,则保持0。

? ? ? ? ? ? ? ? 比如:

????????????????p[j-2]等于'.':dp[i][j]和dp[i-1][j]状态一致

‘’.*a
‘’1010
b0110
c0000
a0000

????????????????p[j-2]等于'.':dp[i][j]和dp[i-1][j]状态一致

‘’.*a
‘’1010
b0110
c0010
a0000

????????????????p[j-2]等于'.':dp[i][j]和dp[i-1][j]状态一致

‘’.*a
‘’1010
b0110
c0010
a0010
?? ? ? ? (2)不看c*:这个时候匹配零个的前面的那一个元素。相当于当这一对c*不存在。

????????????????这个时候就得看??这一对c*的前面的那个字符p[j-3]了,它对应的状态是dp[i][j-2]。因此,这个时候dp[i][j]和dp[i][j-2]状态一致。

? ? ? ? ? ? ? ? 比如:

????????????????不看c*:dp[i][j]和dp[i][j-2]状态一致

‘’.*a
‘’1010
b0000
c0000
a0000

?

?这一步的具体代码:

                if (j > 1 && p[j - 1] == '*')//是*
                {
                    dp[i][j] = dp[i][j] || dp[i][j - 2];//不看c*
                    if (i > 0 && (s[i - 1] == p[j - 2] || p[j - 2] == '.'))//看c*
                        dp[i][j] = dp[i][j] || dp[i - 1][j];//注意这里是dp[i - 1][j]不是dp[i][j - 1]
                }

最后结果:

????????取dp[s.size()][p.size()]

‘’.*a
‘’1010
b0110
c0010
a0011

复杂度计算:

时间复杂度O(nm)

空间复杂度O(nm)

代码:

class Solution {
public:
    bool articleMatch(std::string s, std::string p) {
        std::vector<std::vector<bool>> dp(s.size() + 1, std::vector<bool>(p.size() + 1));
        dp[0][0] = 1;
        for (int i = 0; i < s.size() + 1; ++i)
        {
            for (int j = 0; j < p.size() + 1; ++j)
            {
                if (j > 1 && p[j - 1] == '*')//是*
                {
                    dp[i][j] = dp[i][j] || dp[i][j - 2];//不看c*
                    if (i > 0 && (s[i - 1] == p[j - 2] || p[j - 2] == '.'))//看c*
                        dp[i][j] = dp[i][j] || dp[i - 1][j];//注意这里是dp[i - 1][j]不是dp[i][j - 1]
                }
                else if (i > 0 && j > 0 && (s[i - 1] == p[j - 1] || p[j - 1] == '.'))//不是*
                {
                    dp[i][j] = dp[i - 1][j - 1];
                }
            }
        }
        return dp[s.size()][p.size()];
    }
};

文章来源:https://blog.csdn.net/rainssssss/article/details/135359543
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。