Extend current algorithm to support '+'

  • 0

    Any comments would be appreciated:

    def match(s, p):
        m, n = len(s), len(p)
        dp = [[False for j in range(n+1)] for i in range(m+1)]
        dp[0][0] = True
        for i in range(1, m+1):
            dp[i][0] = False
        for j in range(1, n+1):
            dp[0][j] = (j > 1) and p[j-1] == '*' and dp[0][j-2]
        for i in range(1, m+1):    
            for j in range(1, n+1):    
                if p[j-1] == '+':
                    dp[i][j] = (dp[i-1][j-2] or dp[i-1][j]) and s[i-1] == p[j-2]
                elif p[j-1] != '*':
                    dp[i][j] = dp[i-1][j-1] and (s[i-1] == p[j-1] or p[j-1] == '.')
                    dp[i][j] = dp[i][j-2] or (s[i-1] == p[j-2] or p[j-2] == '.') and dp[i-1][j]
        return dp[m][n]            
    if __name__ == '__main__': 
        assert match('abc', '.*abc') == True
        assert match('abba', 'abba') == True
        assert match('adb', 'cda') == False
        assert match('ababc', '.*abc') == True
        assert match('caaa', '.b*a+') == True
        assert match('baa', 'bb+a*') == False
        assert match('b', 'b+') == True
        assert match('ba', 'b+') == False
        assert match('ab', 'b+') == False
        assert match('ab', 'a+b+') == True

Log in to reply

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