<Hard> Wildcard Matching (LeetCode : C#)

https://leetcode.com/problems/wildcard-matching/

📕 문제 설명

문자열과 pattern이 주어질 때 ?와 * 지원하는 wildcard 매칭 구현

• '?': any single character
• '*': any sequence of characters

• Input
  문자열, 패턴
• Output
  매칭 여부 (bool)

예제

풀이

풀이 1.

재귀 -> 시간 초과

public class Solution {
    public bool IsMatch(string s, string p) {

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

        while (index < pLen && index < sLen && (p[index] == '?' || p[index] == s[index]))
        {
            index ++;
        }

        if (pLen == index) return index == sLen;

        if (p[index] == '*')
        {
            int skip = 0;
            while (skip + index <= sLen)
            {
                if (IsMatch(s.Substring(skip + index, sLen - (skip + index)), p.Substring(index + 1, pLen - (index + 1)))) return true;
                skip++;
            }
        }

        return false;
        
    }
}

public class Solution {
    public bool IsMatch(string s, string p) {

        int sIndex = 0;
        int pIndex = 0;
        int star = -1;
        int m = -1;

        while (sIndex < s.Length)
        {
            // ? 또는 문자 같은 경우 -> 각각 다음 문자확인
            if (pIndex < p.Length && (p[pIndex] == '?' || p[pIndex] == s[sIndex]))
            {
                sIndex++;
                pIndex++;

                continue;
            }
            // p에 *있는 경우 -> p 한칸 움직이기
            if (pIndex < p.Length && p[pIndex] == '*')
            {
                star = pIndex++;
                m = sIndex;

                continue;
            }
            
            // p에 이전에 *나왔던 경우 -> p는 * 다음 나온 문자 보게하고 s 한칸 움직이기
            if (star >= 0)
            {
                pIndex = star + 1;
                sIndex = ++m;

                continue;
            }

            return false;
        }
        // s 먼저 다본경우 p에 *있는 만큼 p 다음칸으로 옮기기
        while (pIndex < p.Length && p[pIndex] == '*') pIndex++;

        return pIndex == p.Length;
        
    }
}

결과