LeetCode 10. Regular Expression Matching

历史记录

清除记录

猜你想搜

AcWing热点
App
登录/注册

LeetCode 10. Regular Expression Matching 原题链接中等

作者：

yxc , 2018-04-19 01:11:44 , 所有人可见 , 阅读 6244

28

4

题目描述

给定一个字符串s和模板串p，实现支持通配符'.'和'*'的正则表达式匹配。

'.' : 可以匹配任意单个字符
'*' : 表示0个或任意多个前一个字符

模板串需要匹配整个字符串。
模板串p一定合法，即'*'前面一定有非'*'字符。

注意：

s可能为空，只包含小写字母a-z
p可能为空，只包含小写字母a-z，以及.和*

样例1

输入：
s = "aa"
p = "a"
输出：false
解释："a"不能匹配整个字符串"aa"

样例2

输入：
s = "aa"
p = "a*"
输出：true
解释：'a*'表示0个或任意多个'a'的时候，可以匹配"aa"

样例3

输入：
s = "ab"
p = ".*"
输入：true
解释：".*"表示0个或任意多个'.'，而'.'可以匹配任意字符，所以p和s可以匹配

样例4

输入：
s = "aab"
p = "c*a*b"
输出：true
解释：这里的p表示0个c、2个a、1个b，可以匹配s

样例5

输入：
s = "mississippi"
p = "mis*is*p*."
输出：false

算法

(动态规划) $O(nm)$

状态表示：f[i][j]表示p从j开始到结尾，是否能匹配s从i开始到结尾
状态转移：

如果p[j+1]不是通配符'*'，则f[i][j]是真，当且仅当s[i]可以和p[j]匹配，且f[i+1][j+1]是真；
如果p[j+1]是通配符'*'，则下面的情况只要有一种满足，f[i][j]就是真；
- f[i][j+2]是真；
- s[i]可以和p[j]匹配，且f[i+1][j]是真；

第1种情况下的状态转移很好理解，那第2种情况下的状态转移怎么理解呢？

最直观的转移方式是这样的：枚举通配符'*'可以匹配多少个p[j]，只要有一种情况可以匹配，则f[i][j]就是真；
这样做的话，我们发现，f[i][j]除了枚举0个p[j]之外，其余的枚举操作都包含在f[i+1][j]中了，所以我们只需判断
f[i+1][j]是否为真，以及s[i]是否可以和p[j]匹配即可。

时间复杂度分析：$n$ 表示s的长度，$m$ 表示p的长度，总共 $nm$ 个状态，状态转移复杂度 $O(1)$，所以总时间复杂度是 $O(nm)$.

C++ 代码

class Solution {
public:
    vector<vector<int>>f;
    int n, m;
    bool isMatch(string s, string p) {
        n = s.size();
        m = p.size();
        f = vector<vector<int>>(n + 1, vector<int>(m + 1, -1));
        return dp(0, 0, s, p);
    }

    bool dp(int x, int y, string &s, string &p)
    {
        if (f[x][y] != -1) return f[x][y];
        if (y == m)
            return f[x][y] = x == n;
        bool first_match = x < n && (s[x] == p[y] || p[y] == '.');
        bool ans;
        if (y + 1 < m && p[y + 1] == '*')
        {
            ans = dp(x, y + 2, s, p) || first_match && dp(x + 1, y, s, p);
        }
        else
            ans = first_match && dp(x + 1, y + 1, s, p);
        return f[x][y] = ans;
    }
};

2 评论

errorer 2019-11-08 15:56

贴一个比较好理解的算法：

class Solution(object):
    def isMatch(self, s, p):
        """
        :type s: str
        :type p: str
        :rtype: bool
        """
        m = len(s)
        pu = []
        start = 0
        #把*和字母合并起来考虑
        while(start < len(p)):
            if start < len(p) - 1 and p[start + 1] == '*':
                pu.append(p[start:start+2])
                start += 2
            else:
                pu.append(p[start])
                start += 1

        pu = pu[::-1] #正向动态规划，，好理解点orz，把s p先倒过来
        s = s[::-1]
        n = len(pu)
        # 增加一个'' 帮助解决边界问题
        f = [[False for _ in range(m + 1)] for _ in range(n + 1)]
        f[0][0] = True
        for i in range(1, m + 1):
            f[0][i] = False
        for i in range(1, n + 1):
            if '*' in pu[i-1] and f[i-1][0] is True:
                f[i][0] = True
            else:
                f[i][0] = False
        for i in range(1, n + 1):
            for j in range(1, m + 1):
                pi = i - 1
                sj = j - 1
                # 当前char 匹配
                if (pu[pi] == s[sj] or pu[pi] == '.') and f[i-1][j-1] is True:
                    f[i][j] = True
                # *匹配，且*所在char匹配
                elif '*' in pu[pi] and (pu[pi][0] == s[sj] or pu[pi][0] == '.'):
                    if f[i-1][j] is True or f[i-1][j-1] is True  or f[i][j-1] is True:
                        f[i][j] = True
                    else:
                        f[i][j] = False
                # *匹配， 但*所在char不匹配。
                elif '*' in pu[pi]:
                    if f[i-1][j] is True:
                        f[i][j] = True
                    else:
                        f[i][j] = False
                #其他情况都不行
                else:
                    f[i][j] = False
        return f[n][m]