leetcode: 10. Regular Expression Matching [✗]

Problem

代码语言：javascript复制

# Implement regular expression matching with support for '.' and '*'.
#
# '.' Matches any single character.
# '*' Matches zero or more of the preceding element.
#
# The matching should cover the entire input string (not partial).
#
# The function prototype should be:
# bool isMatch(const char *s, const char *p)
#
# Some examples:
# isMatch("aa","a") → false
# isMatch("aa","aa") → true
# isMatch("aaa","aa") → false
# isMatch("aa", "a*") → true
# isMatch("aa", ".*") → true
# isMatch("ab", ".*") → true
# isMatch("aab", "c*a*b") → true

AC

代码语言：javascript复制

class Solution():
    def isMatch(self, s, p):
        result = [[False for j in range(len(p)   1)] for i in range(len(s)   1)]

        result[0][0] = True
        for i in range(2, len(p)   1):
            if p[i-1] == '*':
                result[0][i] = result[0][i-2]

        for i in range(1, len(s)   1):
            for j in range(1, len(p)   1):
                if p[j-1] != '*':
                    result[i][j] = result[i-1][j-1] and (s[i-1] == p[j-1] or p[j-1] == '.')
                else:
                    result[i][j] = result[i][j-2] or (result[i-1][j] and (s[i-1] == p[j-2] or p[j-2] == '.'))
        return result[len(s)][len(p)]


if __name__ == "__main__":
    assert Solution().isMatch("abccd", "abc*d") == True
    assert Solution().isMatch("abab", "a*b*") == False
    assert Solution().isMatch("aaaaaaaaaaaaab", "a*a*a*a*a*a*a*a*a*a*c") == False
    assert Solution().isMatch("aa","a") == False
    assert Solution().isMatch("aa","aa") == True
    assert Solution().isMatch("aaa","aa") == False
    assert Solution().isMatch("aa", "a*") == True
    assert Solution().isMatch("aa", ".*") == True
    assert Solution().isMatch("ab", ".*") == True
    assert Solution().isMatch("aab", "c*a*b") == True

express 编程算法

0 人点赞