Recursive DFS solution with memoization (Top Down Approach)
Algorithm:\n- We have two pointers i,j pointing towards S and P.\n- We create a dp[][] where dp[i][j]=1 indicates that 0..ith substring in S has been matched wi
Algorithm:\n- We have two pointers i,j pointing towards `S` and `P`.\n- We create a dp[][] where dp[i][j]=1 indicates that 0..ith substring in `S` has been matched with 0..jth substring in `P`\n- If s[i]==p[j] then we increment both check for s[i+1] and p[j+1]\n- If given char in p is `*` then we have certainly three options\n- either match the current `ith` char in with  `*` in j\n- either end the matching of current `ith` char with `*` and increment both (i,j) -> (i+1,j+1).\n- or match `*` with null characters and increment only `j`.\n```\nclass Solution {\n    \n    Integer[][] dp;\n    public boolean isMatch(String s, String p) {\n         \n        dp = new Integer[s.length()+1][p.length()+1];\n        dp[s.length()][p.length()] = 1;\n        \n        for(int i=p.length()-1;i>=0;--i){\n            dp[s.length()][i] = p.charAt(i)==\'*\'? dp[s.length()][i+1]:0;\n        }\n        \n        for(int j=0;j<s.length();++j){  dp[j][p.length()] = 0;}\n        \n        dfsHelper(s,p,0,0);\n        return dp[0][0]==1;\n        \n    }\n    \n    private int dfsHelper(String s,String p,int sp,int pp){\n        \n        if(dp[sp][pp]!=null){\n            return dp[sp][pp];\n        }\n        \n        if(s.charAt(sp)==p.charAt(pp) || p.charAt(pp)==\'?\'){\n            dp[sp][pp] = dfsHelper(s,p,sp+1,pp+1);\n        }\n        \n        else if(p.charAt(pp)==\'*\'){\n            \n            int resultOne = dfsHelper(s,p,sp+1,pp); // matching seq with *\n            int resultTwo = dfsHelper(s,p,sp,pp+1); // matching * with empty string\n            int resultThree = dfsHelper(s,p,sp+1,pp+1); // end matching seq with * and inc both\n            \n            dp[sp][pp] = (resultOne + resultTwo + resultThree)>0 ? 1:0;\n            \n        }else{\n            dp[sp][pp] = 0;\n        }\n        \n        return dp[sp][pp]; \n    }\n}\n```\n\n![image](https://assets.leetcode.com/users/arihant95/image_1578804311.png)\n\n
['Depth-First Search', 'Memoization']