<Hard> Regular Expression Matching (LeetCode : C#)

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

📕 문제 설명

문자열과 패턴이 주어졌을 때 정규 표현식에 맞는지 확인한다.

.의 경우 아무 문자가 하나 와도 된다.
*의 경우 이전 element 중 0이상의 수만큼 와도 된다.

예제

• Input
  문자열, 패턴
• Output
  (bool) 정규표현식 match 여부

풀이

1. 내장 정규 표현식 사용

using System.Text.RegularExpressions;

public class Solution {
    public bool IsMatch(string s, string p) {
        return new Regex($"^{p}$").IsMatch(s);
    }
}

1. 결과

2. 재귀 사용

public class Solution
{
    public bool IsMatch(string s, string p)
    {
        return IsMatch(0, s, 0, p);
    }
 
    bool IsMatch(int i, string s, int j, string p)
    {
        int pLen = p.Length;
        int sLen = s.Length;
        if (j == pLen) return i == sLen;
        

        bool isFirstMatched = (i < sLen && (p[j] == s[i] || p[j] == '.'));
        
        if (j + 1 < pLen && p[j + 1] == '*') // * 있는 case
        {
            // * 앞 날리고 보기 (ex s = aab & p = c*a*b) or
            // 매칭되는 케이스 (aac & a*c)
            return (IsMatch(i, s, j + 2, p) || (isFirstMatched && IsMatch(i+1, s, j, p)));
        }
        else // * 없는 case
        {
            // 첫번째 같으면 그 뒤 문자 확인하기
            return isFirstMatched && IsMatch(i+1, s, j+1, p);
        }
    }
}

2. 결과

3. 재귀 + 딕셔너리로 이전 결과 저장

딕셔너리로 이전 결과 담고있으면 똑같은 결과에 대해 더 빨리 처리 가능해서 변경해봄 -> 일반 재귀보다 시간 많이 단축

public class Solution {
    public bool IsMatch(string s, string p) {
        var map = new Dictionary<(int i, int j), bool>();
        return IsMatch(map, s, p, 0, 0);
    }

    public bool IsMatch(Dictionary<(int i, int j), bool> map, string s, string p, int i, int j) {
        if(map.ContainsKey((i, j)))
        {
            return map[(i, j)];
        }

        int pLen = p.Length;
        int sLen = s.Length;

        if (j == pLen) return i == sLen;

        bool isFirstMatched = (i < sLen && (p[j] == s[i] || p[j] == '.'));

        if(j+1 < pLen && p[j+1] == '*')
        {
            map[(i, j)] = IsMatch(map, s, p, i, j + 2) || (isFirstMatched && IsMatch(map, s, p, i + 1, j));
            return map[(i, j)];
        }

        if(isFirstMatched)
        {
            map[(i, j)] = IsMatch(map, s, p, i + 1, j + 1);
            return map[(i, j)];
        }

        map[(i, j)] = false;
        return map[(i, j)];
    }
}

3. 결과