题目

Given an input string s and a pattern p, implement regular expression matching with support for ‘.’ and ‘*’ where:

’.’ Matches any single character.​​​​ ‘*’ Matches zero or more of the preceding element. The matching should cover the entire input string (not partial).

Example 1:

Input: s = “aa”, p = “a” Output: false Explanation: “a” does not match the entire string “aa”. Example 2:

Input: s = “aa”, p = “a” Output: true Explanation: ‘’ means zero or more of the preceding element, ‘a’. Therefore, by repeating ‘a’ once, it becomes “aa”. Example 3:

Input: s = “ab”, p = “.” Output: true Explanation: “.” means “zero or more (*) of any character (.)”.

答案

class Solution {
public:
    bool isMatch(string s, string p)
    {

        int ssize = s.size();
        int psize = p.size();
        vector<vector<bool>> dp(ssize,vector<bool>(psize,false));
        vector<bool> marked(psize,false);
        
        for(int j=1;j<psize;j+=2){
            marked[j]=(j==1 && p[j]=='*')||(j!=1&&marked[j-2]&&p[j]=='*');
        }

        for (int i = 0; i < ssize; i++) {

            for (int j=0;j<psize;j++) {
                dp[i][j]=(
                    (s[i]==p[j]||p[j]=='.')&&(((j>0)&&(i>0)&&dp[i-1][j-1])||(j==0&&i==0))
                );
                if (i==0&&j>0&&marked[j-1]&&(p[j]==s[i]||p[j]=='.'))dp[i][j]=true;
                if (i==0&&marked[j]&&(p[j-1]==s[i]||p[j-1]=='.'))dp[i][j]=true;
                if (p[j]=='*'){

                    char reg=p[j-1];
                    if(marked[j]&&reg=='.') dp[i][j]=1;
                    for(int it=i ;it>=0;it--){
                        if (j>1&&dp[it][j-2]){
                            dp[i][j]=true;
                            break;
                        }
                        if (s[it]!=reg&&reg!='.') break;
                        if(it==0&&(j==1||marked[j-2]))dp[i][j]=true;
                    }
                    dp[i][j]=dp[i][j]||(j>1&&dp[i][j-2]);


                }

            }

        }
        return dp.back().back();
    }
};

思路

• 理解题目
  • 题目来自于正则表达式的一种算法，其中.可以替代任意一个字符，表示由前一个字符重复0次或多次。
  • 例如：
    • aa与a匹配失败，因为a只匹配一个字符，而aa匹配两个字符。
    • aa与a*匹配成功，因为a*表示由a重复0次或多次，所以aa可以匹配。
• 基于*可以匹配无数个字符的情况，我们认为这是符合动态规划的形状的，尝试利用动态规划求解。
  • 动态规划的状态转移方程：
    • dp[i][j]表示s的前i个字符与p的前j个字符是否匹配。
  • 对于.和正常的字符，我们可以直接判断是否相等，并不会带来复杂的判断。即dp[i][j]=(s[i]==p[j]||p[j]=='.')&&(((j>0)&&(i>0)&&dp[i-1][j-1])||(j==0&&i==0))

  • 对于*，我们需要考虑多种情况。

    • 首先我们要考虑空串的情况。这一情况在marked数组中有所体现。对于?*?*?*···?*这种情况。每个*对应的位置都是可以接受空串的。其中?代表任意字符。
    • 考虑到?*可以匹配空串，因此当p[j]为*时，dp[i][j]=dp[i][j-2]。
    • 在不匹配空串的情况下，只能匹配s[i]···s[0]当中第一个与p[j-1]不同的字符，如果p[j-1]为.，那就可以一直匹配下去。
  • 观察到marked带来的不变，应当将它整合到dp数组当中。这一过程不在讨论，交由读者自行解决。
• 最后，我们返回dp数组的最后一个元素，即dp[ssize-1][psize-1]，即可判断是否匹配成功。