Python/dynamic_programming/wildcard_matching.py at master · manmita/Python · GitHub

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
"""
Given two strings, an input string and a pattern,
this program checks if the input string matches the pattern.

Example :
input_string = "baaabab"
pattern = "*****ba*****ab"
Output: True

This problem can be solved using the concept of "DYNAMIC PROGRAMMING".

We create a 2D boolean matrix, where each entry match_matrix[i][j] is True
if the first i characters in input_string match the first j characters
of pattern. We initialize the first row and first column based on specific
rules, then fill up the rest of the matrix using a bottom-up dynamic
programming approach.

The amount of match that will be determined is equal to match_matrix[n][m]
where n and m are lengths of the input_string and pattern respectively.

"""


defis_pattern_match(input_string: str, pattern: str) ->bool:
"""
 >>> is_pattern_match('baaabab','*****ba*****ba')
 False
 >>> is_pattern_match('baaabab','*****ba*****ab')
 True
 >>> is_pattern_match('aa','*')
 True
 """

input_length=len(input_string)
pattern_length=len(pattern)

match_matrix= [[False] * (pattern_length+1) for_inrange(input_length+1)]

match_matrix[0][0] =True

forjinrange(1, pattern_length+1):
ifpattern[j-1] =="*":
match_matrix[0][j] =match_matrix[0][j-1]

foriinrange(1, input_length+1):
forjinrange(1, pattern_length+1):
ifpattern[j-1] in ("?", input_string[i-1]):
match_matrix[i][j] =match_matrix[i-1][j-1]
elifpattern[j-1] =="*":
match_matrix[i][j] =match_matrix[i-1][j] ormatch_matrix[i][j-1]
else:
match_matrix[i][j] =False

returnmatch_matrix[input_length][pattern_length]


if__name__=="__main__":
importdoctest

doctest.testmod()

print(f"{is_pattern_match('baaabab','*****ba*****ab')}")
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
"""
Given two strings, an input string and a pattern,
this program checks if the input string matches the pattern.

Example :
input_string = "baaabab"
pattern = "*****ba*****ab"
Output: True

This problem can be solved using the concept of "DYNAMIC PROGRAMMING".

We create a 2D boolean matrix, where each entry match_matrix[i][j] is True
if the first i characters in input_string match the first j characters
of pattern. We initialize the first row and first column based on specific
rules, then fill up the rest of the matrix using a bottom-up dynamic
programming approach.

The amount of match that will be determined is equal to match_matrix[n][m]
where n and m are lengths of the input_string and pattern respectively.

"""


defis_pattern_match(input_string: str, pattern: str) ->bool:
"""
 >>> is_pattern_match('baaabab','*****ba*****ba')
 False
 >>> is_pattern_match('baaabab','*****ba*****ab')
 True
 >>> is_pattern_match('aa','*')
 True
 """

input_length=len(input_string)
pattern_length=len(pattern)

match_matrix= [[False] * (pattern_length+1) for_inrange(input_length+1)]

match_matrix[0][0] =True

forjinrange(1, pattern_length+1):
ifpattern[j-1] =="*":
match_matrix[0][j] =match_matrix[0][j-1]

foriinrange(1, input_length+1):
forjinrange(1, pattern_length+1):
ifpattern[j-1] in ("?", input_string[i-1]):
match_matrix[i][j] =match_matrix[i-1][j-1]
elifpattern[j-1] =="*":
match_matrix[i][j] =match_matrix[i-1][j] ormatch_matrix[i][j-1]
else:
match_matrix[i][j] =False

returnmatch_matrix[input_length][pattern_length]


if__name__=="__main__":
importdoctest

doctest.testmod()

print(f"{is_pattern_match('baaabab','*****ba*****ab')}")
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
"""
Given two strings, an input string and a pattern,
this program checks if the input string matches the pattern.

Example :
input_string = "baaabab"
pattern = "*****ba*****ab"
Output: True

This problem can be solved using the concept of "DYNAMIC PROGRAMMING".

We create a 2D boolean matrix, where each entry match_matrix[i][j] is True
if the first i characters in input_string match the first j characters
of pattern. We initialize the first row and first column based on specific
rules, then fill up the rest of the matrix using a bottom-up dynamic
programming approach.

The amount of match that will be determined is equal to match_matrix[n][m]
where n and m are lengths of the input_string and pattern respectively.

"""


defis_pattern_match(input_string: str, pattern: str) ->bool:
"""
 >>> is_pattern_match('baaabab','*****ba*****ba')
 False
 >>> is_pattern_match('baaabab','*****ba*****ab')
 True
 >>> is_pattern_match('aa','*')
 True
 """

input_length=len(input_string)
pattern_length=len(pattern)

match_matrix= [[False] * (pattern_length+1) for_inrange(input_length+1)]

match_matrix[0][0] =True

forjinrange(1, pattern_length+1):
ifpattern[j-1] =="*":
match_matrix[0][j] =match_matrix[0][j-1]

foriinrange(1, input_length+1):
forjinrange(1, pattern_length+1):
ifpattern[j-1] in ("?", input_string[i-1]):
match_matrix[i][j] =match_matrix[i-1][j-1]
elifpattern[j-1] =="*":
match_matrix[i][j] =match_matrix[i-1][j] ormatch_matrix[i][j-1]
else:
match_matrix[i][j] =False

returnmatch_matrix[input_length][pattern_length]


if__name__=="__main__":
importdoctest

doctest.testmod()

print(f"{is_pattern_match('baaabab','*****ba*****ab')}")
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
"""
Given two strings, an input string and a pattern,
this program checks if the input string matches the pattern.

Example :
input_string = "baaabab"
pattern = "*****ba*****ab"
Output: True

This problem can be solved using the concept of "DYNAMIC PROGRAMMING".

We create a 2D boolean matrix, where each entry match_matrix[i][j] is True
if the first i characters in input_string match the first j characters
of pattern. We initialize the first row and first column based on specific
rules, then fill up the rest of the matrix using a bottom-up dynamic
programming approach.

The amount of match that will be determined is equal to match_matrix[n][m]
where n and m are lengths of the input_string and pattern respectively.

"""


defis_pattern_match(input_string: str, pattern: str) ->bool:
"""
 >>> is_pattern_match('baaabab','*****ba*****ba')
 False
 >>> is_pattern_match('baaabab','*****ba*****ab')
 True
 >>> is_pattern_match('aa','*')
 True
 """

input_length=len(input_string)
pattern_length=len(pattern)

match_matrix= [[False] * (pattern_length+1) for_inrange(input_length+1)]

match_matrix[0][0] =True

forjinrange(1, pattern_length+1):
ifpattern[j-1] =="*":
match_matrix[0][j] =match_matrix[0][j-1]

foriinrange(1, input_length+1):
forjinrange(1, pattern_length+1):
ifpattern[j-1] in ("?", input_string[i-1]):
match_matrix[i][j] =match_matrix[i-1][j-1]
elifpattern[j-1] =="*":
match_matrix[i][j] =match_matrix[i-1][j] ormatch_matrix[i][j-1]
else:
match_matrix[i][j] =False

returnmatch_matrix[input_length][pattern_length]


if__name__=="__main__":
importdoctest

doctest.testmod()

print(f"{is_pattern_match('baaabab','*****ba*****ab')}")
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
"""
Given two strings, an input string and a pattern,
this program checks if the input string matches the pattern.

Example :
input_string = "baaabab"
pattern = "*****ba*****ab"
Output: True

This problem can be solved using the concept of "DYNAMIC PROGRAMMING".

We create a 2D boolean matrix, where each entry match_matrix[i][j] is True
if the first i characters in input_string match the first j characters
of pattern. We initialize the first row and first column based on specific
rules, then fill up the rest of the matrix using a bottom-up dynamic
programming approach.

The amount of match that will be determined is equal to match_matrix[n][m]
where n and m are lengths of the input_string and pattern respectively.

"""


defis_pattern_match(input_string: str, pattern: str) ->bool:
"""
 >>> is_pattern_match('baaabab','*****ba*****ba')
 False
 >>> is_pattern_match('baaabab','*****ba*****ab')
 True
 >>> is_pattern_match('aa','*')
 True
 """

input_length=len(input_string)
pattern_length=len(pattern)

match_matrix= [[False] * (pattern_length+1) for_inrange(input_length+1)]

match_matrix[0][0] =True

forjinrange(1, pattern_length+1):
ifpattern[j-1] =="*":
match_matrix[0][j] =match_matrix[0][j-1]

foriinrange(1, input_length+1):
forjinrange(1, pattern_length+1):
ifpattern[j-1] in ("?", input_string[i-1]):
match_matrix[i][j] =match_matrix[i-1][j-1]
elifpattern[j-1] =="*":
match_matrix[i][j] =match_matrix[i-1][j] ormatch_matrix[i][j-1]
else:
match_matrix[i][j] =False

returnmatch_matrix[input_length][pattern_length]


if__name__=="__main__":
importdoctest

doctest.testmod()

print(f"{is_pattern_match('baaabab','*****ba*****ab')}")
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
"""
Given two strings, an input string and a pattern,
this program checks if the input string matches the pattern.

Example :
input_string = "baaabab"
pattern = "*****ba*****ab"
Output: True

This problem can be solved using the concept of "DYNAMIC PROGRAMMING".

We create a 2D boolean matrix, where each entry match_matrix[i][j] is True
if the first i characters in input_string match the first j characters
of pattern. We initialize the first row and first column based on specific
rules, then fill up the rest of the matrix using a bottom-up dynamic
programming approach.

The amount of match that will be determined is equal to match_matrix[n][m]
where n and m are lengths of the input_string and pattern respectively.

"""


defis_pattern_match(input_string: str, pattern: str) ->bool:
"""
 >>> is_pattern_match('baaabab','*****ba*****ba')
 False
 >>> is_pattern_match('baaabab','*****ba*****ab')
 True
 >>> is_pattern_match('aa','*')
 True
 """

input_length=len(input_string)
pattern_length=len(pattern)

match_matrix= [[False] * (pattern_length+1) for_inrange(input_length+1)]

match_matrix[0][0] =True

forjinrange(1, pattern_length+1):
ifpattern[j-1] =="*":
match_matrix[0][j] =match_matrix[0][j-1]

foriinrange(1, input_length+1):
forjinrange(1, pattern_length+1):
ifpattern[j-1] in ("?", input_string[i-1]):
match_matrix[i][j] =match_matrix[i-1][j-1]
elifpattern[j-1] =="*":
match_matrix[i][j] =match_matrix[i-1][j] ormatch_matrix[i][j-1]
else:
match_matrix[i][j] =False

returnmatch_matrix[input_length][pattern_length]


if__name__=="__main__":
importdoctest

doctest.testmod()

print(f"{is_pattern_match('baaabab','*****ba*****ab')}")
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
"""
Given two strings, an input string and a pattern,
this program checks if the input string matches the pattern.

Example :
input_string = "baaabab"
pattern = "*****ba*****ab"
Output: True

This problem can be solved using the concept of "DYNAMIC PROGRAMMING".

We create a 2D boolean matrix, where each entry match_matrix[i][j] is True
if the first i characters in input_string match the first j characters
of pattern. We initialize the first row and first column based on specific
rules, then fill up the rest of the matrix using a bottom-up dynamic
programming approach.

The amount of match that will be determined is equal to match_matrix[n][m]
where n and m are lengths of the input_string and pattern respectively.

"""


defis_pattern_match(input_string: str, pattern: str) ->bool:
"""
 >>> is_pattern_match('baaabab','*****ba*****ba')
 False
 >>> is_pattern_match('baaabab','*****ba*****ab')
 True
 >>> is_pattern_match('aa','*')
 True
 """

input_length=len(input_string)
pattern_length=len(pattern)

match_matrix= [[False] * (pattern_length+1) for_inrange(input_length+1)]

match_matrix[0][0] =True

forjinrange(1, pattern_length+1):
ifpattern[j-1] =="*":
match_matrix[0][j] =match_matrix[0][j-1]

foriinrange(1, input_length+1):
forjinrange(1, pattern_length+1):
ifpattern[j-1] in ("?", input_string[i-1]):
match_matrix[i][j] =match_matrix[i-1][j-1]
elifpattern[j-1] =="*":
match_matrix[i][j] =match_matrix[i-1][j] ormatch_matrix[i][j-1]
else:
match_matrix[i][j] =False

returnmatch_matrix[input_length][pattern_length]


if__name__=="__main__":
importdoctest

doctest.testmod()

print(f"{is_pattern_match('baaabab','*****ba*****ab')}")
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
"""
Given two strings, an input string and a pattern,
this program checks if the input string matches the pattern.

Example :
input_string = "baaabab"
pattern = "*****ba*****ab"
Output: True

This problem can be solved using the concept of "DYNAMIC PROGRAMMING".

We create a 2D boolean matrix, where each entry match_matrix[i][j] is True
if the first i characters in input_string match the first j characters
of pattern. We initialize the first row and first column based on specific
rules, then fill up the rest of the matrix using a bottom-up dynamic
programming approach.

The amount of match that will be determined is equal to match_matrix[n][m]
where n and m are lengths of the input_string and pattern respectively.

"""


defis_pattern_match(input_string: str, pattern: str) ->bool:
"""
 >>> is_pattern_match('baaabab','*****ba*****ba')
 False
 >>> is_pattern_match('baaabab','*****ba*****ab')
 True
 >>> is_pattern_match('aa','*')
 True
 """

input_length=len(input_string)
pattern_length=len(pattern)

match_matrix= [[False] * (pattern_length+1) for_inrange(input_length+1)]

match_matrix[0][0] =True

forjinrange(1, pattern_length+1):
ifpattern[j-1] =="*":
match_matrix[0][j] =match_matrix[0][j-1]

foriinrange(1, input_length+1):
forjinrange(1, pattern_length+1):
ifpattern[j-1] in ("?", input_string[i-1]):
match_matrix[i][j] =match_matrix[i-1][j-1]
elifpattern[j-1] =="*":
match_matrix[i][j] =match_matrix[i-1][j] ormatch_matrix[i][j-1]
else:
match_matrix[i][j] =False

returnmatch_matrix[input_length][pattern_length]


if__name__=="__main__":
importdoctest

doctest.testmod()

print(f"{is_pattern_match('baaabab','*****ba*****ab')}")