# My DP approach in Python with comments and unittest

• I shared my DP approach with comments and provided some unit tests for it. Some statements in the approach directly affect some corner cases, for example, comment out line 22-23, then the unittest `test_symbol_0` will fail. Hope this script helps us better understand the problem.

``````import unittest

class Solution(object):
def isMatch(self, s, p):
# The DP table and the string s and p use the same indexes i and j, but
# table[i][j] means the match status between p[:i] and s[:j], i.e.
# table[0][0] means the match status of two empty strings, and
# table[1][1] means the match status of p[0] and s[0]. Therefore, when
# refering to the i-th and the j-th characters of p and s for updating
# table[i][j], we use p[i - 1] and s[j - 1].

# Initialize the table with False. The first row is satisfied.
table = [[False] * (len(s) + 1) for _ in range(len(p) + 1)]

# Update the corner case of matching two empty strings.
table[0][0] = True

# Update the corner case of when s is an empty string but p is not.
# Since each '*' can eliminate the charter before it, the table is
# vertically updated by the one before previous. [test_symbol_0]
for i in range(2, len(p) + 1):
table[i][0] = table[i - 2][0] and p[i - 1] == '*'

for i in range(1, len(p) + 1):
for j in range(1, len(s) + 1):
if p[i - 1] != "*":
# Update the table by referring the diagonal element.
table[i][j] = table[i - 1][j - 1] and \
(p[i - 1] == s[j - 1] or p[i - 1] == '.')
else:
# Eliminations (referring to the vertical element)
# Either refer to the one before previous or the previous.
# I.e. * eliminate the previous or count the previous.
# [test_symbol_1]
table[i][j] = table[i - 2][j] or table[i - 1][j]

# Propagations (referring to the horizontal element)
# If p's previous one is equal to the current s, with
# helps of *, the status can be propagated from the left.
# [test_symbol_2]
if p[i - 2] == s[j - 1] or p[i - 2] == '.':
table[i][j] |= table[i][j - 1]

return table[-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()``````

• Thanks for explaining. That's helpful!

• how about "abc" and"a.*".
It seems your program will give a true.

• what if the input string p has two consecutive "*"? Your code seemed to give false

• @whglamrock Consecutive stars are invalid in regex I think.

• @shenggu
Yes I think too. The question description is obviously not clear enough.

• Java version:

``````public class Solution {
public boolean isMatch(String s, String p) {
boolean[][] table = new boolean[p.length() + 1][s.length() + 1];
table[0][0] = true;

for (int i = 2; i <= p.length(); i++) {
table[i][0] = table[i-2][0] && p.charAt(i-1) == '*';

}

for (int i = 1; i <= p.length(); i++) {
for(int j = 1; j <= s.length(); j++) {
if(p.charAt(i-1) != '*') {
table[i][j] = table[i-1][j-1] && (p.charAt(i-1) == s.charAt(j-1) || p.charAt(i-1) == '.');
} else {
table[i][j] = table[i-2][j] || table[i-1][j];
if(p.charAt(i-2) == s.charAt(j-1) || p.charAt(i-2) == '.') {
table[i][j] |= table[i][j-1];
}
}
}
}
return table[p.length()][s.length()];
}
}
``````

Javascript:

``````var isMatch = function(s, p) {
var table = new Array(p.length + 1);
for(var i = 0; i < table.length; i++) {
table[i] = new Array(s.length + 1);
table[i].fill(false)
}
table[0][0] = true;

for (var i = 2; i <= p.length; i++) {
table[i][0] = table[i-2][0] && p[i-1] == '*';
}

for (var i = 1; i <= p.length; i++) {
for(var j = 1; j <= s.length; j++) {
if(p[i-1] != '*') {
table[i][j] = table[i-1][j-1] && (p[i-1] == s[j-1] || p[i-1] == '.');
} else {
table[i][j] = table[i-2][j] || table[i-1][j];
if(p[i-2] == s[j-1] || p[i-2] == '.') {
table[i][j] |= table[i][j-1];
}
}
}
}
return table[p.length][s.length]==1 ? true:false
};
``````

Golang:

``````func isMatch(s string, p string) bool {
table := make([][]bool, len(p) + 1)
for i := 0; i < len(table); i++ {
table[i] = make([]bool, len(s) + 1)
for j := 0; j < len(table[i]); j++ {
table[i][j] = false
}
}

table[0][0] = true

for i := 2; i <= len(p); i++ {
table[i][0] = table[i-2][0] && p[i-1] == '*';
}

for i := 1; i <= len(p); i++ {
for j := 1; j <= len(s); j++ {
if p[i-1] != '*' {
table[i][j] = table[i-1][j-1] && (p[i-1] == s[j-1] || p[i-1] == '.')
} else {
table[i][j] = table[i-2][j] || table[i-1][j]
if p[i-2] == s[j-1] || p[i-2] == '.' {
if table[i][j-1] {
table[i][j] = true
}
}
}
}
}
return table[len(p)][len(s)]
}
``````

• @cwl Thanks for sharing! I am trying to understand your solution. Why `table[i][j] = table[i - 2][j] or table[i - 1][j]`? It seems that `table[i][j] = table[i - 2][j]` still works?

• @Chengcheng.Pei You are right. The elimination logic could be simplified. Here is the code I recently rewrote it. Hope this helps.

``````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]
``````

• Nice explanation with comments. Thank you

• The situation `or table[i - 1][j]` is already contained in `if p[i - 2] == s[j - 1] or p[i - 2] == '.': table[i][j] |= table[i][j - 1]`.

• ``````        dp = [[True] + [False] * len(s)]
for i, pc in enumerate(p):
row = [pc == '*' and dp[-2][0]]
for j, sc in enumerate(s):
if pc == '.':
row.append(dp[-1][j])
elif pc == '*':
row.append(dp[-2][j + 1] or ((p[i - 1] == '.' or p[i - 1] == sc) and row[j]))
else:
row.append(dp[-1][j] and pc == sc)
dp.append(row)
return dp[-1][-1]
``````

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.