✅EASIEST JAVA SOLUTION✅||🚀BEATS 99.87%🚀||🔥O(m x n) 🔥
SMALL REQUEST : If you find this post even remotely helpful, be kind enough to smash a upvote. I will be grateful & motivated. Thank you.\uD83D\uDE0A\uD83D\uDE0
# SMALL REQUEST : If you find this post even remotely helpful, be kind enough to smash a upvote. I will be grateful & motivated. Thank you.\uD83D\uDE0A\uD83D\uDE0A\n\n# Approach\n- Here\'s a step-by-step explanation of your dynamic programming approach for wildcard pattern matching:\n\n  1. Create a 2D boolean array dp with dimensions (p.length()+1) x (s.length()+1). dp[i][j] will represent whether the pattern p starting from index i matches the input string s starting from index j.\n\n  2. Initialize the base cases:\n  For i = p.length() (when pattern is empty), and j = s.length() (when input is empty), dp[i][j] is set to true since an empty pattern matches an empty string.\nFor i = p.length() (when pattern is empty) and any valid j, dp[i][j] is set to false since a non-empty input string can\'t match an empty pattern.\nFor j = s.length() (when input is empty) and any valid i, you need to check if the pattern consists of only *. If yes, then it matches the empty string, otherwise, it doesn\'t match.\n  3. Fill in the dp array by considering the characters of the pattern and the input string one by one, starting from the last characters of each:\n  4. If p.charAt(i) is a ?, the result depends on whether the rest of the pattern (p[i+1:]) matches the rest of the input string (s[j+1:]). Therefore, dp[i][j] is set to dp[i+1][j+1].\n  5. If p.charAt(i) is a *, you have two choices:\nYou can consider the * as matching zero characters in the input string, i.e., dp[i][j] depends on dp[i+1][j].\nYou can consider the * as matching one or more characters in the input string, i.e., dp[i][j] depends on dp[i][j+1].\nTherefore, dp[i][j] is set to dp[i+1][j] || dp[i][j+1].\n  6. If p.charAt(i) is a regular character and matches s.charAt(j), then the result depends on whether the rest of the pattern and input string match (dp[i][j] is set to dp[i+1][j+1]).\n  7. If p.charAt(i) is a regular character but doesn\'t match s.charAt(j), then dp[i][j] is set to false.\n  8. The final answer is stored in dp[0][0], which represents whether the entire pattern p matches the entire input string s.\n\n# Complexity\n- **Time complexity :**\nThe time complexity of your code is **O(m * n)**, where m is the length of the pattern string p and n is the length of the input string s. This is because you are using a nested loop to iterate over all possible combinations of characters in p and s, and for each combination, you perform constant time operations.\n\n- **Space complexity:**\nThe space complexity of your code is also **O(m * n)**, where m is the length of the pattern string p and n is the length of the input string s. This is because you are using a 2D boolean array dp with dimensions (m+1) x (n+1) to store intermediate results for dynamic programming. Each cell in the array requires constant space, and since you have (m+1) x (n+1) cells, the overall space complexity is O(m * n).\n\n# Code\n```\nclass Solution {\n    public boolean isMatch(String s, String p) {\n        boolean dp[][] = new boolean[p.length()+1][s.length()+1];\n        for(int i = dp.length-1; i >= 0; i--) {\n            for(int j = dp[0].length-1; j >= 0; j--) {\n                if(i == dp.length-1 && j == dp[0].length-1) {\n                    dp[i][j] = true;\n                } else if(i == dp.length-1) {\n                    dp[i][j] = false;\n                } else if(j == dp[0].length-1) {\n                    if(p.charAt(i) == \'*\') {\n                        dp[i][j] = dp[i+1][j];\n                    } else {\n                        dp[i][j] = false;\n                    }\n                } else {\n                    if(p.charAt(i) == \'?\') {\n                        dp[i][j] = dp[i+1][j+1];\n                    } else if(p.charAt(i) == \'*\') {\n                        dp[i][j] = dp[i+1][j] || dp[i][j+1];\n                    } else if(p.charAt(i) == s.charAt(j)) {\n                        dp[i][j] = dp[i+1][j+1];\n                    } else {\n                        dp[i][j] = false;\n                    }\n                }\n            }\n        }\n        return dp[0][0];\n    }\n}\n\n```\n# THANK YOU.\uD83D\uDE0A![5f6aee89-454b-47ff-93c9-7030eb5d3673_1694227000.9068315.jpg](https://assets.leetcode.com/users/images/709d0c14-8874-4577-ab95-e75574cf7458_1694256507.3541515.jpeg)\n
['String', 'Dynamic Programming', 'Greedy', 'Recursion', 'Java']