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:
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:
=>次の部分の一致を検索Reference
この問題について(10. Regular Expression Matching - python3), 我々は、より多くの情報をここで見つけました https://velog.io/@jsh5408/10.-Regular-Expression-Matching-python3テキストは自由に共有またはコピーできます。ただし、このドキュメントのURLは参考URLとして残しておいてください。
Collection and Share based on the CC Protocol