LeetCode 44. Wildcard MatchingProblemGiven an input string s and a pattern p, implement wildcard pattern matching with support for:· ‘?’ — Matches any single character.· ‘*’ — Matches any sequence of characters (including the empty sequence).The matching should cover the entire string s.Approach: Dynamic ProgrammingLet dp[i][j] represent whether the first i characters of s match the first j characters of p.Transitions:· If p[j-1] ‘?’ or s[i-1] p[j-1]:dp[i][j] dp[i-1][j-1]· If p[j-1] ‘*’:dp[i][j] dp[i-1][j] || dp[i][j-1]· dp[i-1][j]: * matches empty sequence.· dp[i][j-1]: * matches the current character of s.Base cases:· dp[0][0] true· dp[0][j] true if p[0…j-1] are all ‘*’· dp[i][0] false for i 0We can optimize space to O(n) using a 1D array.Java ImplementationclassSolution{publicbooleanisMatch(Strings,Stringp){intms.length();intnp.length();boolean[]dpnewboolean[n1];// Base case: empty string matches empty patterndp[0]true;// Initialize for empty string sfor(intj1;jn;j){if(p.charAt(j-1)*){dp[j]dp[j-1];}}for(inti1;im;i){booleanprevdp[0];// dp[i-1][0]dp[0]false;// dp[i][0] false for i 0for(intj1;jn;j){booleantempdp[j];// save dp[i-1][j]charpcp.charAt(j-1);charscs.charAt(i-1);if(pc*){// dp[i][j] dp[i-1][j] (star matches empty)// || dp[i][j-1] (star matches current char)dp[j]dp[j]||dp[j-1];}elseif(pc?||pcsc){dp[j]prev;}else{dp[j]false;}prevtemp;}}returndp[n];}}ExampleInput:sadcebp*a*bOutput:trueExplanation: The first * matches empty, a matches a, the second * matches dce, and b matches b.Complexity AnalysisMetric ComplexityTime O(m * n)Space O(n)Where m s.length() and n p.length().Key Points‘?’ matches exactly one character.‘*’ can match zero or more characters.The 1D DP array reuses the previous row and updates in place.The prev variable stores dp[i-1][j-1] to avoid overwriting it before use.