[leetcode][10] Regular Expression Matching

문제 : leetcode.com/problems/regular-expression-matching/

---

문자열 s와 패턴 p가 주어질 때 문자열 s가 패턴 p에 매칭되는지 판단하라.

패턴의 경우 나올 수 있는 문자는 총 3가지로,  .   *   소문자 알파벳  이 있다.

 .  : 어떤 문자가 와도 매칭된다.

 *  : 바로 앞에 나온 패턴 문자와 0개 이상 매칭된다.

 소문자 알파벳  : 동일한 문자인 경우 매칭된다.

 . 

---

backtracking으로 구현. 2차원 배열을 만들어 memoization 해줬다.

. 과 알파벳 소문자의 패턴인 경우는 문제될게 없다.

. 는 무조건 통과이므로 s, p 모두 다음 문자를 확인한다.

소문자 알파벳은 다르다면 false, 같다면 다음 문자를 확인한다.

 

문제는 *.

s = "aaaabb". p = "a*bb".

라 해보자.

첫번째 확인 문자는 s, p 각각 a, a인데. 패턴 p는 * 가 있으므로 확인중인 문자의 다음 문자도 확인한다.

두번째 p 문자열의 문자가 * 이므로 a 문자를 0번이상 s 문자열의 문자와 달라질때까지 비교한다.

0 번 : s = "aaaabb". p = "a*bb". -> false

1 번 : s = "aaaabb". p = "a*bb". -> false

2 번 : s = "aaaabb". p = "a*bb". -> false

3 번 : s = "aaaabb". p = "a*bb". -> false

4 번 : s = "aaaabb". p = "a*bb". -> true

5번 : aaaabb, aaaaa는 다른 패턴이므로 false.

 

만약 모든 패턴 문자열의 확인이 끝났는데 아직 확인하지 못한 s 문자열이 있다면 false.

모든 s 문자열을 매칭여부가 확인이 끝났는데 패턴 문자열이 남은 경우는 추가로 확인이 필요하다.

만약 남은 패턴 문자열들중 . 나 알파벳 소문자 패턴이 있는 경우는 false.

남은 패턴 문자열들이 모두 _* 패턴(_ 는 아무 문자라 가정)이라면 0번 매칭또한 true이므로 최종매칭 결과는 true가 된다.

 

시간복잡도는 s문자열의 길이를 N이라 했을 때 * 패턴 때문에 O(N^2). 

---

소스코드 : github.com/fpdjsns/Algorithm/blob/master/leetcode/hard/10.%20Regular%20Expression%20Matching.cpp

---

문자열 패턴 매칭 문제는 언제 풀어도 새롭네..