[Leetcode] [미결] 10. Regular Expression Matching

1. 문제

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



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


Constraints:

1 <= s.length <= 20
1 <= p.length <= 20
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.

 

---

2. 배운점

 

---

3. 내 풀이

기본 Run을 통과하고 나머지 case들을 검토하다가 문제를 잘못 파악하고 있었다는 것을 알게 됐다. 문제가 어려워서 결국 풀이법을 보게됐다. 다음에 다시 볼 때는 학습한 내용을 기억하고 있기를!

 

궁금했던 점 기록

1. 2개의 문자열 또는 리스트의 요소를 하나씩 비교해야할 때 for문 말고 적절한 방법이 있을까? 그리고 2개 중 어떤게 긴지 판단하는데 좋은 방법이 있을까? 실무에서도 많이 쓰일 수 있을 것 같다.
2. 아래 case 주석에 적어놓은 것처럼 여러가지 case가 복잡하게 존재할 때 이것을 과연 일일이 if문으로 처리해야할까? 엄청나게 복잡한 현실 문제면 모르겠으나 뭔가 방법이 있기 때문에 문제로 출제된 것이 아닐까 의심해봐야할 것 같다. 그런다고 경험해보지 못한 해법이 금방 튀어나올 것 같지는 않지만...

class Solution:
    def isMatch(self, s: str, p: str) -> bool:
        # p, s 길이 긴걸로 돌면서 분기
        if len(s) >= len(p):
            for s_idx, s_ch in enumerate(s):
                for p_idx, p_ch in enumerate(p):
                    if s_ch == p_ch:
                        if p[p_idx + 1] == '*':
                                 
                    if s_ch != p_ch:
                        continue
                        
        # case s= aab, p=c*a*b
        # case s= a**b, p=c*a*b
        # 1. s == p 
        # 2. p == .
        # 3. s != p / s != p and next_p == *

 

 

4. 해법

- 힌트

- Dynamic programming, recursion

 

- 링크

https://leetcode.com/problems/regular-expression-matching/solutions/3243200/beats-98-regular-expression-matching-using-dynamic-programming-in-python/

 

- 풀이 보기

 

class Solution:
    def isMatch(self, s: str, p: str) -> bool:
        memo = {}
    
        def dp(i: int, j: int) -> bool:
            if (i, j) in memo:
                return memo[(i, j)]
        
            if j == len(p):
                return i == len(s)
        
            first_match = i < len(s) and (p[j] == s[i] or p[j] == '.')
        
            if j + 1 < len(p) and p[j+1] == '*':
                ans = dp(i, j+2) or (first_match and dp(i+1, j))
            else:
                ans = first_match and dp(i+1, j+1)
        
            memo[(i, j)] = ans
            return ans
    
        return dp(0, 0)

 

---

 

참조

 

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