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

关键词：动态规划

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

题目：

思路：

dp状态：

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

初始状态：

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

如下表格所示

	‘’	.	*	a
‘’	1	0	0	0
b	0	0	0	0
c	0	0	0	0
a	0	0	0	0

转移方程：

假如我们需要确认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
‘’	1	0	1	0
b	0	1	0	0
c	0	0	0	0
a	0	0	0	0

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

	‘’	.	*	a
‘’	1	0	1	0
b	0	1	1	0
c	0	0	0	0
a	0	0	0	0

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

	‘’	.	*	a
‘’	1	0	1	0
b	0	1	1	0
c	0	0	1	0
a	0	0	1	1

这一步的具体代码：

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
‘’	1	0	1	0
b	0	1	1	0
c	0	0	0	0
a	0	0	0	0

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

	‘’	.	*	a
‘’	1	0	1	0
b	0	1	1	0
c	0	0	1	0
a	0	0	0	0

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

	‘’	.	*	a
‘’	1	0	1	0
b	0	1	1	0
c	0	0	1	0
a	0	0	1	0

?? ? ? ? （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
‘’	1	0	1	0
b	0	0	0	0
c	0	0	0	0
a	0	0	0	0

?

?这一步的具体代码：

                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
‘’	1	0	1	0
b	0	1	1	0
c	0	0	1	0
a	0	0	1	1

复杂度计算：

时间复杂度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()];
    }
};