Java Recursion and DP
Fristly, the recursive solution is pretty easy: \n\nclass Solution \n{\n    public boolean isMatch(String s, String p) \n    {\n        return match(s, 0, p, 0)
Fristly, the recursive solution is pretty easy: \n```\nclass Solution \n{\n    public boolean isMatch(String s, String p) \n    {\n        return match(s, 0, p, 0);\n    }\n    \n    boolean match(String s, int i, String p, int j)\n    {\n        if (i == s.length() && j == p.length()) return true;\n        if (j == p.length()) return false;\n        if (i == s.length())\n        {\n            // the remaining in p are *\n            for (int k = j; k < p.length(); ++k) if (p.charAt(k) != \'*\') return false;\n            return true;\n        }\n        \n        if (p.charAt(j) == \'*\')\n        {\n            // the * could match 0+ chars in s\n            return match(s, i + 1, p, j) || match(s, i, p, j + 1);\n        }\n        else\n        {\n            if (p.charAt(j) == \'?\' || s.charAt(i) == p.charAt(j))\n            {\n                return match(s, i + 1, p, j + 1);\n            }\n            return false;\n        }\n    }\n}\n```\n\nAfter that, rewrite it to DP:\n```\nclass Solution \n{\n    public boolean isMatch(String s, String p) \n    {   \n        // init base cases\n        int m = s.length(), n = p.length();\n        boolean[][] f = new boolean[m + 1][n + 1];\n        f[m][n] = true;\n        for (int j = n - 1; j >= 0; --j) if (p.charAt(j) == \'*\') f[m][j] = true; else break;\n        \n        // DP\n        for (int i = m - 1; i >= 0; --i)\n        {\n            for (int j = n - 1; j >= 0; --j)\n            {\n                if (p.charAt(j) == \'*\') f[i][j] = f[i][j + 1] || f[i + 1][j];\n                else if (p.charAt(j) == \'?\' || s.charAt(i) == p.charAt(j)) f[i][j] = f[i + 1][j + 1];\n            }\n        }\n        \n        return f[0][0];\n    }\n}\n```
[]