class Solution:
    # Helper function to check if first i characters are all '*'
    def isAllStars(self, S1, i):
        # Loop from index 0 to i-1
        for j in range(1, i + 1):
            # If any character is not '*', return False
            if S1[j - 1] != '*':
                return False
        # All were '*', so return True
        return True

    # Function to check if S1 matches S2
    def wildcardMatching(self, S1, S2):
        # Lengths of pattern and text
        n = len(S1)
        m = len(S2)

        # Create DP table with default False
        dp = [[False] * (m + 1) for _ in range(n + 1)]

        # Base case: empty pattern matches empty string
        dp[0][0] = True

        # Base case: empty pattern cannot match non-empty string
        for j in range(1, m + 1):
            dp[0][j] = False

        # Base case: pattern can match empty string if it has all '*'
        for i in range(1, n + 1):
            dp[i][0] = self.isAllStars(S1, i)

        # Fill DP table
        for i in range(1, n + 1):
            for j in range(1, m + 1):

                # Case 1: Exact match or '?'
                if S1[i - 1] == S2[j - 1] or S1[i - 1] == '?':
                    dp[i][j] = dp[i - 1][j - 1]

                # Case 2: '*'
                elif S1[i - 1] == '*':
                    # Zero characters OR one/more characters
                    dp[i][j] = dp[i - 1][j] or dp[i][j - 1]

                # Case 3: No match
                else:
                    dp[i][j] = False

        # Return final answer
        return dp[n][m]


# Driver code
if __name__ == "__main__":
    sol = Solution()
    S1 = "ab*cd"
    S2 = "abdefcd"

    result = sol.wildcardMatching(S1, S2)
    if result:
        print("String S1 and S2 do match")
    else:
        print("String S1 and S2 do not match")

12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152535455565758596061626364656667686970

class Solution {
    // Helper function to check if first i characters are all '*'
    isAllStars(S1, i) {
        for (let j = 1; j <= i; j++) {
            if (S1[j - 1] !== '*') {
                return false;
            }
        }
        return true;
    }

    // Function to check if S1 matches S2
    wildcardMatching(S1, S2) {
        const n = S1.length;
        const m = S2.length;

        // Create 2D array filled with false
        const dp = Array.from({ length: n + 1 }, () => Array(m + 1).fill(false));

        // Base case: empty pattern matches empty string
        dp[0][0] = true;

        // Base case: empty pattern cannot match non-empty string
        for (let j = 1; j <= m; j++) {
            dp[0][j] = false;
        }

        // Base case: pattern matches empty string if it has all '*'
        for (let i = 1; i <= n; i++) {
            dp[i][0] = this.isAllStars(S1, i);
        }

        // Fill DP