[LeetCode] Regular Expression Matching

문제

Given an input string (s) and a pattern (p), implement regular expression matching with support for '.' and '*'.'.' Matches any single character. '*' Matches zero or more of the preceding element.

The matching should cover the entire input string (not partial).

Note:

• s could be empty and contains only lowercase letters a-z.
• p could be empty and contains only lowercase letters a-z, and characters like . or *.

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

 

Approach

regex_match()를 쓴다

처음엔 if문으로 조건 만족하게 열심히 짰지만

*가 경우의 수가 너무 많아진다는게 문제였다. (*앞에 문자를 안쓸수도 있고 쓸수도 있다는 것 때문에)

도저히 모르겠어서 Solution을 봤더니 앞에서 부터 한 글자씩 맞춰보고 *가 나오면

1. *를 무시한다

2. *로 text의 글자를 처리하고 다음 글자를 읽는다

로 나눠서 recursive하게 풀어나간다.

이런 문제는 경험 안해보면 풀이를 떠올리기기 쉽지 않을 것 같다.

 

Optimization

Recursive 할때 text의 i번째 글자부터 pattern의 j번째 글자로 처리할 때 match가 되냐 안되냐를

저장해두고 다음 계산에서 이 결과를 활용하는 DP를 쓰면 속도를 더 올릴 수 있다.

 

Code

Recursive

https://github.com/chi3236/algorithm/blob/master/LeetCode_RegularExpressionMatching.cpp 

chi3236/algorithm

Recursive + DP

https://github.com/chi3236/algorithm/blob/master/LeetCode_RegularExpressionMatchingDP.cpp

chi3236/algorithm