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]

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*"