[LeetCode/릿코드] - 10. Regular Expression Matching - (Hard/하드)

문제 :

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

문제 해설 : 

이번 문제는 어려워서,, 다른 코드를 조금 참고 했다.
Dynamic Programming / Recursion 으로 풀 수 있는데, 처음에 구현 문제라고 생각한 것이 문제였다.

주어지는 문자열 s 와 p 가 맞는지 확인하는 문제, 
p에 주어지는 문자 중에 특별히, ' . ', ' * ' 는 규칙이 존재한다.

' . ' dot : 어떠한 문자 1개를 대신할 수 있다.
' * ' asterisk : 해당 기호 앞의 문자를 대신할 수 있고, 개수는 0 부터 무한이다.
즉 s에는 있어도 없어도 상관 없으며, 많아도 ' * ' 가 모두 처리 가능하다.

문제 아이디어 :

처음에 ' . ' 와 ' * ' 를 보고 구현이다 싶었다, 아무리 구현하려고 해도 버그가 나와서 안되고 보니. 
관련 주제가 Recursion, Dynamic Programming 이다... 결국 정답 힌트를 보고, DP말고 재귀로 풀어 보았다.

1. 크게 두가지로 재귀를 호출한다. ' * ' 일때랑 아닐때,
2. ' * ' 일때, 0 개여도 되니까 앞 문자와 ' * ' 를 날려버리는 경우와, 매칭 될때, 그리고 앞 문자가 ' . ' 일때,
3. 요렇게 ' * ' 를 처리해주고, ' . ' 일때나, 문자가 맞을때를 처리해주면 완료.

* Time Limit 가 발생해서 보니, 재귀 호출을 적절하게 설계해야 했으며, 처음 부터 s, p 를 어떻게 잘라서 매개 변수로 넘길지 고민해봐야한다. 즉 p 에서 2개 빠질때, s 에서 1개 빠지고 p 보존, s 와 p 하나씩 빼서 전달. 재귀호출의 가지(브랜치) 가 많아지면 안된다. 

Example 1:

Input: s = "aa", p = "a" Output: false Explanation: "a" does not match the entire string "aa".

Example 2:

Input: s = "aa", p = "a*" Output: true Explanation: '*' means zero or more of the preceding element, 'a'. Therefore, by repeating 'a' once, it becomes "aa".

Example 3:

Input: s = "ab", p = ".*" Output: true Explanation: ".*" means "zero or more (*) of any character (.)".

Example 4:

Input: s = "aab", p = "c*a*b" Output: true Explanation: c can be repeated 0 times, a can be repeated 1 time. Therefore, it matches "aab".

Example 5:

Input: s = "mississippi", p = "mis*is*p*." Output: false

 

Constraints:

• 1 <= s.length <= 20
• 1 <= p.length <= 30
• s contains only lowercase English letters.
• p contains only lowercase English letters, '.', and '*'.
• It is guaranteed for each appearance of the character '*', there will be a previous valid character to match.

 

제한 :

길이 자체가 20, 30 이다보니, 재귀 호출 즉 O(2 ^ n) 에 시간 초과과 나는 것을 미리 고민 하자.
테스트케이스를 넣으면서 발견한거기도 한데 , 제한의 마지막줄에 이전 글자는 유효해야한다는 말이 ' * ' 가 연속으로 나오면 안되는 것 같다. 

 

정답 코드

class Solution:
    def isMatch(self, s: str, p: str) -> bool:
        def rec(ss: str, pp: str) -> bool:
            if not pp and not ss:
                return True
            if not pp :
                return False
            ppLen = len(pp)
            ssLen = len(ss)
            if ppLen > 1 and pp[1] == '*':
                if rec(ss, pp[2:]) == True:
                    return True
                if ssLen > 0 and (ss[0] == pp[0] or pp[0] == '.'):
                    return rec(ss[1:], pp)
            else:
                if ssLen > 0 and (ss[0] == pp[0] or pp[0] == '.'):
                    return rec(ss[1:], pp[1:]) 
            return False
        return rec(s, p)