10. Regular Expression Matching - python3

1975 ワード

10. Regular Expression Matching


Given an input string (s) and a pattern (p), implement regular expression matching with support for '.' and '*' where:
  • '.' Matches any single character.​​​​
  • '*' Matches zero or more of the preceding element.
    The matching should cover the entire input string (not partial).
  • My Answer 1: Wrong Answer

    class Solution:
        def isMatch(self, s: str, p: str) -> bool:
            result = False
            i = 0
            j = 0
            while i < len(s)-2 and j < len(p)-1:
                k = i
                if s[i] == p[j] and p[j+1] == '*':
                    while s[i] == s[i+1]:
                        i += 1
                    else:
                        i += 1
                    j += 1
                elif p[j] == '.':
                    continue
                else:
                    if p[j+1] == '*':
                        j += 2
            
            if i < len(s) or j < len(p):
                return False
            else:
                return True
    状況を全部考えて、条件文をめちゃくちゃにしたいのですが...
    制限範囲が長すぎるので諦めます...ほほほ

    Recursion


    Solution 1: Runtime: 1204 ms - 21.64% / Memory Usage: 14.2 MB - 80.99%

    class Solution:
        def isMatch(self, s: str, p: str) -> bool:
            if not p:
                return not s
            
            # s 가 빈 문자열인지 아닌지 & p[0] 가 s[0] or . 인지 확인 => T/F
            first_match = bool(s) and p[0] in {s[0], '.'}
            
            # s 에서 반복되는 부분만큼 재귀 돌려서 찾기
            if len(p) >= 2 and p[1] == '*':
                return (self.isMatch(s, p[2:]) or
                        first_match and self.isMatch(s[1:], p))
            else:
                # [0] 부분이 match 되면 다음 부분을 재귀 돌림
                return first_match and self.isMatch(s[1:], p[1:])
    if len(p) >= 2 and p[1] == '*':=>重複部分の検索else:=>次の部分の一致を検索