[LeetCode] 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).

 

문자열 s와 패턴 p가 주어졌을 때, s가 p에 매칭되는지 확인하는 문제이다.

 

패턴에서 "."은 아무 문자 하나, "*"은 앞의 문자 반복(0, 1 포함)을 의미한다.

---

 

풀이

---

아이디어

".", "*"이 정규표현식과 같은 역할을 하기 때문에 그냥 정규표현식을 쓰면 될 것이다.다만, 문제의 p는 "**" 같이 *이 반복되는 형태를 허용하고, 정규표현식에선 허용하지 않기 때문에 이를 처리해야 한다.

 

코드

import re

class Solution:
    def isMatch(self, s: str, p: str) -> bool:

        # *이 반복되는 부분을 없애줌
        p_before = ""
        while p_before != p:
            p_before = p
            p = p.replace("**", "*")

        pp = re.compile(p)

        return pp.match(s) and pp.match(s).group() == s

---

 

후기

---

난이도

정규표현식을 알고 있다면 무척이나 쉬운 문제이다.

 

문자열 전체가 패턴에 매칭되야 하고, *이 반복된다는 것만 신경쓰면 어렵지 않게 풀 수 있을 것이다.

 

다른 풀이

정규표현식을 사용하지 않고, 문자열을 앞에서 부터 살펴보며 "."과 "*"에 대한 처리를 한다면 조금 복잡해질 수 있지 않을까 싶다.