剑指52-正则表达式匹配

实现正则表达式匹配、动态规划

题目描述

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

解法

要判断当前pattern字符和str当前字符是否匹配，要看他们之前字符的状态

定义一个动态数组dp[str.size()+1][pattern.size()+1]，全初始化为0，假如str当前位置i，pattern当前位置j

情况1：pattern[j-1]!=’‘，即前一个字符不为’\‘

1：pattern[j-1]=='.'，即匹配串前一个字符为'.'，因为'.'可以匹配一个字符，所以dp[i][j]=dp[i-1][j-1]

2: pattern[j-1]==str[i-1]，即前一个字符是相同的，也是匹配一个字符，dp[i][j]=dp[i-1][j-1]

3： pattern[j-1]！=str[i-1]，即前一个字符是不匹配的，那dp[i-1][j-1]肯定是0，dp[i][j]也肯定是0，这个情况不用管

情况2： pattern[j-1]==’‘，即前一个字符为’\‘，然后以下两种可能的情况，只要有一种成立即可

1：匹配0个字符：dp[i][j]=dp[i][j-2]

2: 匹配1或多个个字符：dp[i][j]=dp[i-1][j]

初始化dp数组：考虑当pattern在位置0时，如果str不在位置0则匹配失败，如果str在位置0则匹配成功

考虑越界情况，保证下标不会越界

class Solution {
public:
    bool match(char* s, char* p)
    {
        int sn = strlen(s), pn = strlen(p);
        vector<vector<char>> dp(sn+1, vector<char>(pn+1, 0));
        for (int i=0; i<=sn; ++i) {
            for (int j=0; j<=pn; ++j) {
                // 初始条件
                if (j == 0) dp[i][j] = (i == 0);
                else {
                    // 如果没有 '*'
                    if (p[j-1] != '*') {
                        if (i >= 1 && j>=1 && (s[i-1] == p[j-1] || p[j-1] == '.')) {
                            dp[i][j] = dp[i-1][j-1];
                        }
                    }
                    // 如果有 '*'
                    else {
                        // 重复 0 次
                        if (j >= 2) {
                            dp[i][j] |= dp[i][j-2];
                        }
                        // 重复 1 次或者多次
                        // 这里要用 | 连接， 不然重复 0 次的会直接覆盖
                        if (i >= 1 && j>=2 && (s[i-1] == p[j-2] || p[j-2] == '.')) {
                            dp[i][j] |= dp[i-1][j];
                        }
                    }
                }

            }
        }
        return dp[sn][pn];
    }
};