My DP approach in Python with comments and unittest


  • 64
    C

    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()

  • 0
    T

    Thanks for explaining. That's helpful!


  • 0
    W

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


  • 0
    W

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


  • 0
    S

    @whglamrock Consecutive stars are invalid in regex I think.


  • 0
    W

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


  • 0
    R

    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)]
    }
    

  • 0
    C

    @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?


  • 0
    C

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

  • 0
    S

    Nice explanation with comments. Thank you


  • 0

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


  • 0
    I
            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]
    

Log in to reply
 

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