Leetcode 10. Regular Expression Matching (정규표현식, Dynamic Programming)

문제. input string s과 '.'와 '*'가 포함된 정규표현식  pattern p가 주어졌을 때, matching이 전체 input string을 포함하는지 여부를 반환하라

 

https://leetcode.com/problems/regular-expression-matching/

Regular Expression Matching - LeetCode

 

---

풀이방법)

import re
class Solution:
    def isMatch(self, s: str, p: str) -> bool:
        pattern = re.compile(p)
        return pattern.fullmatch(s)

저는 사실 정규표현식을 사용해서 matching여부를 반환했는데요

re.fullmatch()의 경우 Python 3.4부터 포함되는 기능으로, 문자열이 pattern과 일치하면 일치하는 객체를 반환하고 아니면 None을 반환합니다.

 

re.fullmatch 대신 re.search와 re.match를 대신 쓸 수 있는데요, 헷갈리는 search()와 match()를 간단히 정리해보겠습니다

**정규표현식 re.match 와 re.match비교
re.match == > 문자열의 시작 부분에서만! 일치를 검사함
re.search ==> 모든 문자열에서 일치여부를 검사함

예시)
re.match("c","abcdef") -> no matching
re.search("c","abcdef") -> matching

re.match("^c","abc") -> matching
re.search("^c","abc") -> no matching

 

https://docs.python.org/ko/3/library/re.html#re.search

re — 정규식 연산 — Python 3.10.7 문서

 

---

문제는 비교적 수월하게 풀었지만 , 답변을 보니 이 문제는 Dynamic Programming에 대한 난이도 hard의 문제였습니다...

Discussion에 제시된 풀이를 보면서 문제의 의도를 다시 파악해보겠습니다

 

Array를 사용한 방법

class Solution(object):
	def isMatch(self,s,p):
    	prev = [False,True]
        for j in range(len(p)):
        	prev.append(p[j] == '*' and prev[j])
        
        for i in range(len(s)):
        	curr = [False,False]
            for j in range(len(p)):
            	if p[j] == '*':
                	curr.append(curr[j] or curr[j+1] or (prev[j+2] and p[j-1] in (s[i],'.')))
                else:
                	curr.append(prev[j+1] and p[j] in (s[i],'.'))
            prev = curr
        return prev[-1]

 

Dynamic Programming Table을 이용한 방법

Class Solution:
	def isMatch(self, s, p):
    	T = [False for _ in range(len(s)+1)] for _ in range(len(p)+1)]
        
        T[0][0] = True
        
        for i in range(1,len(p)+1):
        	T[i][0] = i > 1 and T[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] == s[j-1] or p[i-1] == '.':
                	T[i][j] |= T[i-1][j-1]
                    
                elif p[i-1] == '*':
                	T[i][j] |= T[i-1][j-1]
                    T[i][j] |= i > 1 and T[i-2][j]
                    
                  	if i>1 and p[i-2] == s[j-1] or p[i-2] == '.':
                    	T[i][j] |= T[i][j-1]
       return T[-1][-1]

 

(Dynamic Programming에 대한 내용은 별도 정리 후 업데이트 하겠습니다.)