regular expression matching – leetcode a10

Problem

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).

The function prototype should be:
bool isMatch(const char s, const char p)

Some examples:
isMatch(“aa”,”a”) → false
isMatch(“aa”,”aa”) → true
isMatch(“aaa”,”aa”) → false
isMatch(“aa”, “a“) → true
isMatch(“aa”, “.“) → true
isMatch(“ab”, “.“) → true
isMatch(“aab”, “ca*b”) → true

Analysis

dp[i, j] = true if s[i:] == p[j:]

dp[i, j] = dp[i, j+2] or first_matched and dp[i+1, j] if j+1 < len(p) and p[j+1] == ‘*’.

dp[i, j] = first_matched and dp[i+1, j+1], otherwise

first_matched = p[j] in {s[i], ‘.’}

Python Implementation

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

class :
def isMatch(self, s, p):
"""
:type s: str
:type p: str
:rtype: bool
"""

cache = {}
def dp(i, j):
if (i, j) not in cache:
if (j == len(p)):
ans = (i == len(s))
else:
first = i < len(s) and p[j] in {s[i], '.'}
if j + 1 < len(p) and p[j + 1] == '*':
ans = dp(i, j + 2) or first and dp(i+1, j)
else:
ans = first and dp(i+1, j+1)
cache[(i,j)] = ans
return cache[(i,j)]
return dp(0, 0)

Python Implementation

regular expression matching – leetcode a10

Problem

Analysis

近期文章

近期评论

标签

热门

文章归档

分类目录

功能