forked from kamyu104/LeetCode-Solutions
-
Notifications
You must be signed in to change notification settings - Fork 1
/
regular-expression-matching.py
100 lines (85 loc) · 3.34 KB
/
regular-expression-matching.py
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
# Time: O(m * n)
# Space: O(n)
class Solution(object):
# @return a boolean
def isMatch(self, s, p):
k = 3
result = [[False for j in xrange(len(p) + 1)] for i in xrange(k)]
result[0][0] = True
for i in xrange(2, len(p) + 1):
if p[i-1] == '*':
result[0][i] = result[0][i-2]
for i in xrange(1,len(s) + 1):
if i > 1:
result[0][0] = False
for j in xrange(1, len(p) + 1):
if p[j-1] != '*':
result[i % k][j] = result[(i-1) % k][j-1] and (s[i-1] == p[j-1] or p[j-1] == '.')
else:
result[i % k][j] = result[i % k][j-2] or (result[(i-1) % k][j] and (s[i-1] == p[j-2] or p[j-2] == '.'))
return result[len(s) % k][len(p)]
# dp
# Time: O(m * n)
# Space: O(m * n)
class Solution2(object):
# @return a boolean
def isMatch(self, s, p):
result = [[False for j in xrange(len(p) + 1)] for i in xrange(len(s) + 1)]
result[0][0] = True
for i in xrange(2, len(p) + 1):
if p[i-1] == '*':
result[0][i] = result[0][i-2]
for i in xrange(1,len(s) + 1):
for j in xrange(1, len(p) + 1):
if p[j-1] != '*':
result[i][j] = result[i-1][j-1] and (s[i-1] == p[j-1] or p[j-1] == '.')
else:
result[i][j] = result[i][j-2] or (result[i-1][j] and (s[i-1] == p[j-2] or p[j-2] == '.'))
return result[len(s)][len(p)]
# iteration
class Solution3(object):
# @return a boolean
def isMatch(self, s, p):
p_ptr, s_ptr, last_s_ptr, last_p_ptr = 0, 0, -1, -1
last_ptr = []
while s_ptr < len(s):
if p_ptr < len(p) and (p_ptr == len(p) - 1 or p[p_ptr + 1] != '*') and \
(s_ptr < len(s) and (p[p_ptr] == s[s_ptr] or p[p_ptr] == '.')):
s_ptr += 1
p_ptr += 1
elif p_ptr < len(p) - 1 and (p_ptr != len(p) - 1 and p[p_ptr + 1] == '*'):
p_ptr += 2
last_ptr.append([s_ptr, p_ptr])
elif last_ptr:
[last_s_ptr, last_p_ptr] = last_ptr.pop()
while last_ptr and p[last_p_ptr - 2] != s[last_s_ptr] and p[last_p_ptr - 2] != '.':
[last_s_ptr, last_p_ptr] = last_ptr.pop()
if p[last_p_ptr - 2] == s[last_s_ptr] or p[last_p_ptr - 2] == '.':
last_s_ptr += 1
s_ptr = last_s_ptr
p_ptr = last_p_ptr
last_ptr.append([s_ptr, p_ptr])
else:
return False
else:
return False
while p_ptr < len(p) - 1 and p[p_ptr] == '.' and p[p_ptr + 1] == '*':
p_ptr += 2
return p_ptr == len(p)
# recursive
class Solution4(object):
# @return a boolean
def isMatch(self, s, p):
if not p:
return not s
if len(p) == 1 or p[1] != '*':
if len(s) > 0 and (p[0] == s[0] or p[0] == '.'):
return self.isMatch(s[1:], p[1:])
else:
return False
else:
while len(s) > 0 and (p[0] == s[0] or p[0] == '.'):
if self.isMatch(s, p[2:]):
return True
s = s[1:]
return self.isMatch(s, p[2:])