[LeetCode 풀이/python] 10. Regular Expression Matching (hard)

문제 설명: 입력 문자열 s 와 패턴 p 가 주어졌을 때, '.' 와 '*' 을 활용하여 정규 표현식 매칭을 구현하시오. 입력 문자열의 (일부가 아닌) 전체를 커버할 수 있어야만 매칭되는 것으로 간주함. ('.' 는 임의의 한 문자에 매칭될 수 있고, '*' 는 선행 요소가 0 개 이상인 것과 매칭됨) 

 

(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).)

 

예시 1)

입력: s = "aa", p = "a"  --> 출력: false

설명: "a" 는 전체 문자열 "aa" 와 매칭되지 않음

 

예시 2)

입력: s = "aa", p = "a*"  --> 출력: true

설명: "*" 는 선행 요소 'a' 가 0개 이상 존재하는 것을 의미하므로, 'a' 를 한 번 반복하면 p 는 "aa" 로 볼 수 있음

 

예시 3)

입력: s = "ab", p = ".*"  --> 출력: true

설명: ".*" 는 임의의 한 문자 '.' 가 0개 이상 존재("*") 하는 것이므로 p 를 '..' 로 간주하면 매칭 가능

 

예시 4)

입력: s = "aab", p = "c*a*b"  --> 출력: true

설명: 첫번째 "*" 에 의해 c 가 0번 반복되고, 두번째 "*" 에 의해 a 가 2번 반복되면 매칭 가능

 

예시 5)

입력: s = "mississippi", p = "mis*is*p*."  --> 출력: false

 

제한 조건:

• 0 <= s.length <= 20 & 0 <= p.length <= 30
• s 는 영문 소문자만을 포함
• p 는 영문 소문자 또는 '.' 와 '*' 만을 포함
• 문자 '*' 가 등장하는 경우에는 항상 이와 매칭되는 유효한 문자가 선행하고 있음을 보장

 

 

------ * ------ * ------ * ------

 

[풀이 1안]

• 접근법
  • Regular expression matching 문제이니 Regular expression 을 써본다
  • re.compile() 은 매칭 기준이 되는 패턴을 컴파일 하는 함수. 이걸 이용해서 대상 문자열 s 에 대해 주어진 패턴과 일치하는 요소를 모두 찾아내는 r.findall() 함수를 적용하면 대상 문자열에서 패턴과 매칭되는 내역을 리스트로 저장 (cand)
  • 우리의 목적은 주어진 패턴이 한방에(...) 전체 문자열과 매칭되는 것인지를 확인하는 것이므로, true 를 리턴하려면 cand 에는 문자열 s 와 동일한 문자열이 단 하나 저장되어 있어야 함!

 

• 코드 구현

import re

def isMatch(s: str, p: str) -> bool:
    r = re.compile(p)
    cand = r.findall(s)
    
    if (len(cand) > 0) and (cand[0] == s):
        return True
    else:
        return False

 

• 결과
  • 확실히 re 라이브러리를 활용하니 아주 간결한 코드로 풀리긴 함 (파이썬 내장함수 만세...!)
  • 다만 어디선가 정규표현식 관련 함수들이 은근히 Computation cost 를 많이 필요로 한다고 들었는데, 그 때문인지 런타임 면에서는 보다 효율화된 접근이 필요해 보임!

 

[풀이 2안]

• 접근법
  • Discussions 를 확인해보니 DP 를 활용한 접근이 효율적인 솔루션이 될 수 있는 것으로 보임
  • DP memoization 테이블 dp 을 만들어 문자열 s 의 i 번째 문자까지와 패턴 p 의 j 번째 문자까지가 매칭되는지 여부를 dp[i][j] 에 저장함!
    • dp[i][j] 가 true 이기 위해서는 dp[i-1][j-1] 가 true 임이 전제되어야 하므로 recursively 확인하는 것이 효율적
    • 문자열 s, 패턴 p 가 각각 empty string 인 경우도 (출발점으로서) 고려해야 함!  -->  (len(s) + 1) * (len(p) + 1) 형태의 dp 테이블 구축 필요
    • dp[i][j] 를 구하기 위해 p[i-1] & s[j-1] 값을 확인해야 하는 것이 은근히 헷갈리는 부분 (...)

 

• 코드 구현

def isMatch(s, p):
    dp = [[False] * (len(s) + 1) for _ in range(len(p) + 1)]

    # 코너 케이스 1: s, p 모두 empty string 인 경우 매칭 되는 것이므로
    dp[0][0] = True

    # 코너 케이스 2: s 만 empty string 이고 p 는 아닌 경우
    # dp[i][0] 는 s 가 empty string 인 경우를 가리킴
    # '*' 는 항상 선행 요소가 있는 상황을 전제 & 직전에 나온 문자를 제거할 수 있음 -> 2부터 시작
    for i in range(2, len(p) + 1):
        dp[i][0] = dp[i - 2][0] and p[i - 1] == '*'

    # 본격 recursively dp 테이블 채우기
    for i in range(1, len(p) + 1):
        for j in range(1, len(s) + 1):
        
            # 패턴 p 의 i 번째 문자가 '*' 이 아닌 경우 (영문자 or '.')
            # i-1 번째까지 매칭 결과가 true 이고 동시에 (영문자가 일치하거나 . 인 경우)
            if p[i - 1] != "*":
                dp[i][j] = dp[i - 1][j - 1] and (p[i - 1] == s[j - 1] or p[i - 1] == '.')
            
            # 패턴 p 의 i 번째 문자가 '*' 인 경우
            else:
                # 자기 자신이 empty string 이 되거나 직전 문자를 제거하게 되는 경우
                dp[i][j] = dp[i - 1][j] or dp[i - 2][j]

                # '*' 이전에 등장한 문자가 현재 s 의 j 번째 문자와 같거나 '.' 였을 경우
                if p[i - 2] == s[j - 1] or p[i - 2] == '.':
                    dp[i][j] |= dp[i][j - 1]

        return dp[-1][-1]

 

• 결과
  • DP 방식을 활용할 경우 런타임이 줄어드는 것을 확인
  • 구조적으로 케이스를 잘 나누어 꼼꼼하게 따져 본 것 자체가 대단... (풀이 보고 겨우 이해했다 ㅜㅜ) 

 

## 참고 출처: 

leetcode.com/problems/regular-expression-matching/discuss/5723/My-DP-approach-in-Python-with-comments-and-unittest