FazBrowse GitHub Viewer
|
Trending
|
URL:
|
Home
Tools:
[Download Repo ZIP]
[View Raw Code]
[Original HTTPS Page]
algorithms/dp/regex_matching.py at master · pedkather/algorithms · GitHub
pedkather
algorithms
Repository navigation
Code
Pull requests
Actions
Projects
Wiki
Security and quality
Insights
Expand file tree
Breadcrumbs
algorithms
/
dp
/
regex_matching.py
Copy path
More file actions
More file actions
Latest commit
History
History
History
107 lines (87 loc) · 2.96 KB
Breadcrumbs
algorithms
/
dp
/
regex_matching.py
Copy path
File metadata and controls
107 lines (87 loc) · 2.96 KB
Raw
Copy raw file
Download raw file
Open symbols panel
Edit and raw actions
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
100
101
102
103
104
105
106
107
"""
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", "c*a*b") → true
"""
class
Solution
(
object
):
def
isMatch
(
self
,
s
,
p
):
m
,
n
=
len
(
s
)
+
1
,
len
(
p
)
+
1
matches
=
[[
False
]
*
n
for
_
in
range
(
m
)]
# Match empty string with empty pattern
matches
[
0
][
0
]
=
True
# Match empty string with .*
for
i
,
element
in
enumerate
(
p
[
1
:],
2
):
matches
[
0
][
i
]
=
matches
[
0
][
i
-
2
]
and
element
==
'*'
for
i
,
ss
in
enumerate
(
s
,
1
):
for
j
,
pp
in
enumerate
(
p
,
1
):
if
pp
!=
'*'
:
# The previous character has matched and the current one
# has to be matched. Two possible matches: the same or .
matches
[
i
][
j
]
=
matches
[
i
-
1
][
j
-
1
]
and
\
(
ss
==
pp
or
pp
==
'.'
)
else
:
# Horizontal look up [j - 2].
# Not use the character before *.
matches
[
i
][
j
]
|=
matches
[
i
][
j
-
2
]
# Vertical look up [i - 1].
# Use at least one character before *.
# p a b *
# s 1 0 0 0
# a 0 1 0 1
# b 0 0 1 1
# b 0 0 0 ?
if
ss
==
p
[
j
-
2
]
or
p
[
j
-
2
]
==
'.'
:
matches
[
i
][
j
]
|=
matches
[
i
-
1
][
j
]
return
matches
[
-
1
][
-
1
]
class
TestSolution
(
unittest
.
TestCase
):
def
test_none_0
(
self
):
s
=
""
p
=
""
self
.
assertTrue
(
Solution
().
isMatch
(
s
,
p
))
def
test_none_1
(
self
):
s
=
""
p
=
"a"
self
.
assertFalse
(
Solution
().
isMatch
(
s
,
p
))
def
test_no_symbol_equal
(
self
):
s
=
"abcd"
p
=
"abcd"
self
.
assertTrue
(
Solution
().
isMatch
(
s
,
p
))
def
test_no_symbol_not_equal_0
(
self
):
s
=
"abcd"
p
=
"efgh"
self
.
assertFalse
(
Solution
().
isMatch
(
s
,
p
))
def
test_no_symbol_not_equal_1
(
self
):
s
=
"ab"
p
=
"abb"
self
.
assertFalse
(
Solution
().
isMatch
(
s
,
p
))
def
test_symbol_0
(
self
):
s
=
""
p
=
"a*"
self
.
assertTrue
(
Solution
().
isMatch
(
s
,
p
))
def
test_symbol_1
(
self
):
s
=
"a"
p
=
"ab*"
self
.
assertTrue
(
Solution
().
isMatch
(
s
,
p
))
def
test_symbol_2
(
self
):
# E.g.
# s a b b
# p 1 0 0 0
# a 0 1 0 0
# b 0 0 1 0
# * 0 1 1 1
s
=
"abb"
p
=
"ab*"
self
.
assertTrue
(
Solution
().
isMatch
(
s
,
p
))
if
__name__
==
"__main__"
:
unittest
.
main
()
Back
|
FazBrowse Home
|
New Git URL