Coding LeetCode

LeetCode 10. Regular Expression Matching

查阅更多的题解,请点击

Problem

Regular Expression Matching

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

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

Note:

  • s could be empty and contains only lowercase letters a-z.
  • p could be empty and contains only lowercase letters a-z, and characters like . or *.

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 precedeng 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 (.)".

Example 4:

Input:
s = "aab"
p = "c*a*b"
Output: true
Explanation: c can be repeated 0 times, a can be repeated 1 time. Therefore it matches "aab".

Example 5:

Input:
s = "mississippi"
p = "mis*is*p*."
Output: false

Solution

这道题比较麻烦,该匹配问题实际上是判断两个字符串是否相同的问题,不过由于加入通配符*(可匹配不同长度的字符串),遍历比较并不可取 按照算法笔记中的技巧来进行分析:首先进行两种比较容易的观察,显然,问题解为是否匹配,不具有可以枚举的形式;所以观察问题是否可以reduce,问题input是string,可以看做是字符数组,对于input是数组的问题,观察是否可以reduce时有以下的方式:

  • 从中间分作两个小数组,显然对问题分析没有帮助
  • 从小规模问题出发,由于该问题input为两个数组,定义小规模问题的方式并不是通常的前i个元素:定义[i,j]为字符串s中的前i个元素与p中的前j个元素是否匹配,OPT[i,j]为该子问题的解,则对于[i+1,j+1]可以得出以下的递归表达式(note:s[i-1]代表的是s字符串的第i个元素

OPT[i+1,j+1]=\left{ \begin{array}{rcl} OPT[i,j] & & {if\ p[j]!=’_’\ and\ (s[i]==p[j]||p[j]==’.’)}\ OPT[i+1,j] & & {p[j]==’_’\ and\ the\ pattern\ repeats\ for\ 0\ time}\ OPT[i,j+1]&&(s[i-1]==p[i-1]||p[i-1]=’.’) & & {p[j]==’*’\ and\ the\ pattern\ repeats\ for\ 1\ time} \end{array} \right.

上述递归表达式已经很好的描述了该问题(pattern 重复超过1次的可以递归表示),则可以采用动态规划对问题求解,此时需要注意的是递归的边界条件

  • 如果p访问结束,则当且仅当s也访问结束时匹配成功
  • 如果p访问未结束,而s为全部访问完成,则p之后的元素必须为’*’且the pattern repeats for 0 time,这时匹配成功

在上述递归表达式中,OPT[i+1,j+1]的结果不仅与之前计算的子问题的结果相关,还与之前的元素比较的结果相关,用递归的方式实现较为复杂

GitHub传送门

class Solution
{
  private:
  public:
    bool isMatch(string s, string p)
    {
       int m = s.size(), n = p.size();
        vector<vector<bool>> opt(m + 1, vector<bool>(n + 1, false));
        opt[0][0] = true;
        for (int i = 0; i <= m; i++) {
            for (int j = 1; j <= n; j++) {
                if (p[j - 1] == '*') {
                    opt[i][j] = opt[i][j - 2] || (i && opt[i - 1][j] && (s[i - 1] == p[j - 2] || p[j - 2] == '.'));
                } else {
                    opt[i][j] = i && opt[i - 1][j - 1] && (s[i - 1] == p[j - 1] || p[j - 1] == '.');
                }
            }
        }
        return opt[m][n];
    }
};

发表评论

您的电子邮箱地址不会被公开。 必填项已用*标注