Evolve from brute force to optimal
This is similar to regular expression matching  but more tricky.\n1. Recursion O(2^n), * matches 0 or more chars.\n\n    bool isMatch(string s, string p) {\n   
This is similar to [regular expression matching ](https://discuss.leetcode.com/topic/54908/evolve-from-brute-force-to-dp) but more tricky.\n1. Recursion O(2^n), * matches 0 or more chars.\n```\n    bool isMatch(string s, string p) {\n        return isMatch(0,0,s,p);    \n    }\n    bool isMatch(int i, int j, string& s, string& p) {\n        int sn = s.size();\n        if(j==p.size()) return i==sn;\n        if(p[j]==\'*\') {\n            for(int k=i;k<=sn;k++) if(isMatch(k,j+1,s,p)) return 1;\n            return 0;\n        }\n        if(i<sn && (p[j]==\'?\'||s[i]==p[j])) return isMatch(i+1,j+1,s,p);\n        return 0;\n    }\n```\n2. Use recursion instead of iteration when * matches non empty string, O(2^n)\n* c++\n```\n    bool isMatch(string s, string p) {\n        return isMatch(0,0,s,p);    \n    }\n    bool isMatch(int i, int j, string& s, string& p) {\n        int sn = s.size();\n        if(j==p.size()) return i==sn;\n        if(p[j]==\'*\') return isMatch(i,j+1,s,p) || (i<sn && isMatch(i+1,j,s,p));\n        if(i<sn && (p[j]==\'?\'|| s[i]==p[j])) return isMatch(i+1,j+1,s,p);\n        return 0;\n    }\n```\n* java\n```\n\tpublic boolean isMatch(String s, String p) {\n        return isMatch(0, s, 0, p);\n    }\n    private boolean isMatch(int i, String s, int j, String p) {\n        int sn = s.length(), pn = p.length();\n        if(j==pn) {\n            return i==sn;\n        }\n        char pj = p.charAt(j);\n        if(i<sn && pj == \'?\') {\n            return isMatch(i+1, s, j+1, p);\n        } else if(pj == \'*\') {\n            return isMatch(i,s,j+1,p) || i<sn && isMatch(i+1,s,j,p);   \n        } else if(i<sn && pj == s.charAt(i)) {\n            return isMatch(i+1, s, j+1, p);\n        }\n        return false;\n    }\n```\n3. Memorization O(n^2), memorization turns out to be faster than dp. I think it is because dfs terminates as soon as a match is found but dp is always n^2.  \n* c++\n```\n    bool isMatch(string s, string p) {\n        vector<vector<char>> mem(s.size()+1,vector<char>(p.size(),-1));\n        return isMatch(0,0,s,p,mem);    \n    }\n    bool isMatch(int i, int j, string& s, string& p,vector<vector<char>> &mem) {\n        int sn = s.size();\n        if(j==p.size()) return i==sn;\n        if(mem[i][j]!=-1) return mem[i][j];\n        if(p[j]==\'*\') return mem[i][j]= isMatch(i,j+1,s,p,mem) || (i<sn && isMatch(i+1,j,s,p,mem));\n        if(i<sn && (p[j]==\'?\'|| s[i]==p[j])) return mem[i][j]=isMatch(i+1,j+1,s,p,mem);\n        return mem[i][j]=0;\n    }\n```\n* java\n```\n\tBoolean[][] mem;\n    public boolean isMatch(String s, String p) {\n        mem = new Boolean[s.length()+1][p.length()+1];\n        return isMatch(0, s, 0, p);\n    }\n    private boolean isMatch(int i, String s, int j, String p) {\n        int sn = s.length(), pn = p.length();\n        if(j==pn) {\n            return i==sn;\n        }\n        if(mem[i][j] != null) {\n            return mem[i][j];\n        }\n        char pj = p.charAt(j);\n        if(i<sn && pj == \'?\') {\n            return mem[i][j] = isMatch(i+1, s, j+1, p);\n        } else if(pj == \'*\') {\n            return mem[i][j] = isMatch(i,s,j+1,p) || i<sn && isMatch(i+1,s,j,p);   \n        } else if(i<sn && pj == s.charAt(i)) {\n            return mem[i][j] = isMatch(i+1, s, j+1, p);\n        }\n        return mem[i][j] = false;\n    }\n```\n4. dp O(n^2)\n```\n    bool isMatch(string s, string p) {\n        int sn = s.size(), pn = p.size();\n        vector<vector<bool>> dp(sn+1,vector<bool>(pn+1));\n        dp[sn][pn]=1;\n        for(int i=sn;i>=0;i--)\n            for(int j=pn-1;j>=0;j--)\n                if(p[j]==\'*\') dp[i][j] = dp[i][j+1]||(i<sn && dp[i+1][j]);\n                else dp[i][j] = i<sn && (p[j]==\'?\'|| s[i]==p[j]) && dp[i+1][j+1]; \n        return dp[0][0];    \n    }\n```\n5. For most recursion to dp problems, we are done. However, we can still do better in this problem. For each star, we match it incrementally with 0, 1, 2 ... chars. If a path fails, we only need to backtrack from the last star. Backtracking from earlier stars eats more chars in s and leaves a shorter string for the last star. This does not create any more choices for the last star. More formally, \n\n\t*Say we use #1 and have 2 stars in p separated by characters. When we reach the 2nd star for the first time, there is a match right before it between s(0...i) and p(0......j). s(0...i) is the first/shortest substring that matches p(0...j) because we match  to chars incrementally. Matching the 2nd star starts from s[i+1]. If we backtrack the 1st star and match it with more characters then the next time when s(0...k) matche s p(0...j), k must be larger than i. At this point, matching the 2nd star starts from s[k+1]. Since k>i, so it is covered by just backtracking the 2nd star. Therefore backtracking the 1st star does not create more opportunities and we can ignore it.*\n\n* c++ Code is based on #1.\n```\n    bool isMatch(string s, string p) {\n        bool star = 0;\n        return isMatch(star,0,0,s,p);    \n    }\n    bool isMatch(bool& star, int i, int j, string& s, string& p) {\n        int sn = s.size();\n        if(j==p.size()) return i==sn;\n        if(p[j]==\'*\') {\n            for(int k=i;k<=sn;k++) {\n                if(isMatch(star,k,j+1,s,p)) return 1;\n                if(star) return 0;\n            }\n            star = 1;\n            return 0;\n        }\n        if(i<sn && (p[j]==\'?\'||s[i]==p[j])) return isMatch(star,i+1,j+1,s,p);\n        return 0;\n    }\n```\n* java\n```\n\t int lastStar;\n    public boolean isMatch(String s, String p) {\n        lastStar = -1;\n        return isMatch(0, s, 0, p);\n    }\n    private boolean isMatch(int i, String s, int j, String p) {\n        int sn = s.length(), pn = p.length();\n        if(j==pn) {\n            return i==sn;\n        }\n        char pj = p.charAt(j);\n        if(i<sn && pj == \'?\') {\n            return isMatch(i+1, s, j+1, p);\n        } else if(pj == \'*\') {\n            lastStar = j;\n            return isMatch(i,s,j+1,p) || i<sn && j==lastStar && isMatch(i+1,s,j,p);   \n        } else if(i<sn && pj == s.charAt(i)) {\n            return isMatch(i+1, s, j+1, p);\n        }\n        return false;\n    }\n```\n6. Iterative backtracking O(n^2), same as #4. [Idea is from the top solution](https://discuss.leetcode.com/topic/3040/linear-runtime-and-constant-space-solution)\n```\n    bool isMatch(string s, string p) {\n        int i=0,j=0,star=-1,si=0;\n        while(i<s.size()) {\n            if(p[j]==\'?\'||s[i]==p[j]) {\n                i++;\n                j++;\n            } else if (p[j]==\'*\') {\n                star = j++;\n                si = i;\n            } else if (star >=0 ) {\n                i = ++si;\n                j = star+1;\n            } else return 0;\n        }\n        while(j<p.size()) if(p[j++]!=\'*\') return 0;\n        return 1;\n    }\n```
['C']