<p>Given an input string (<code>s</code>) and a pattern (<code>p</code>), implement wildcard pattern matching with support for <code>&#39;?&#39;</code> and <code>&#39;*&#39;</code> where:</p>

<ul>
	<li><code>&#39;?&#39;</code> Matches any single character.</li>
	<li><code>&#39;*&#39;</code> Matches any sequence of characters (including the empty sequence).</li>
</ul>

<p>The matching should cover the <strong>entire</strong> input string (not partial).</p>

<p>&nbsp;</p>
<p><strong class="example">Example 1:</strong></p>

<pre>
<strong>Input:</strong> s = &quot;aa&quot;, p = &quot;a&quot;
<strong>Output:</strong> false
<strong>Explanation:</strong> &quot;a&quot; does not match the entire string &quot;aa&quot;.
</pre>

<p><strong class="example">Example 2:</strong></p>

<pre>
<strong>Input:</strong> s = &quot;aa&quot;, p = &quot;*&quot;
<strong>Output:</strong> true
<strong>Explanation:</strong>&nbsp;&#39;*&#39; matches any sequence.
</pre>

<p><strong class="example">Example 3:</strong></p>

<pre>
<strong>Input:</strong> s = &quot;cb&quot;, p = &quot;?a&quot;
<strong>Output:</strong> false
<strong>Explanation:</strong>&nbsp;&#39;?&#39; matches &#39;c&#39;, but the second letter is &#39;a&#39;, which does not match &#39;b&#39;.
</pre>

<p>&nbsp;</p>
<p><strong>Constraints:</strong></p>

<ul>
	<li><code>0 &lt;= s.length, p.length &lt;= 2000</code></li>
	<li><code>s</code> contains only lowercase English letters.</li>
	<li><code>p</code> contains only lowercase English letters, <code>&#39;?&#39;</code> or <code>&#39;*&#39;</code>.</li>
</ul>

from functools import lru_cache

class Solution:
    def isMatch(self, s: str, p: str) -> bool:
        n, m = len(s), len(p)

        if m == 0:
            return n == 0

        if m > 0 and n == 0:
            return p == '*' * m  # 패턴이 모두 '*'일 경우에만 True

        return self.isMatchingHelper(s, p, 0, 0)

    @lru_cache(None)
    def isMatchingHelper(self, s: str, p: str, i: int, j: int) -> bool:
        n, m = len(s), len(p)

        if j == m:
            return i == n  # 패턴이 끝났을 때, 문자열도 끝나야 함

        if i == n:
            # 남은 패턴이 모두 '*'인지 확인
            return all(x == '*' for x in p[j:])

        # Handle non '*' characters
        if p[j] == s[i] or p[j] == '?':
            return self.isMatchingHelper(s, p, i + 1, j + 1)
        elif p[j] == '*':
            # '*'가 0개 또는 여러 개의 문자를 매칭할 수 있는 경우
            return self.isMatchingHelper(s, p, i, j + 1) or self.isMatchingHelper(s, p, i + 1, j)

        return False

# 테스트 코드
sol = Solution()
print(sol.isMatch("aa", "*"))        # 출력: True
print(sol.isMatch("aa", "a"))        # 출력: False
print(sol.isMatch("cb", "?a"))       # 출력: False
print(sol.isMatch("adceb", "*a*b"))  # 출력: True
print(sol.isMatch("acdcb", "a*c?b")) # 출력: False

155890