Java solution -- O(n^2) DP solution with some explanations
I had a solution for "Regular Expression Matching" problem: https://leetcode.com/discuss/66032/java-solution-o-n-2-dp-with-some-explanations.\n\nSlight change t
I had a solution for "Regular Expression Matching" problem: https://leetcode.com/discuss/66032/java-solution-o-n-2-dp-with-some-explanations.\n\nSlight change to that solution gives an O(n^3) DP solution for this "Wildcard Matching" problem:\n\n    // O(n^3) DP solution for understanding the algorightm:\n    public boolean isMatch(String s, String p) {\n        int sL = s.length(), pL = p.length();\n        \n        boolean[][] dp = new boolean[sL+1][pL+1];\n        dp[0][0] = true; // If s and p are "", isMathch() returns true;\n        \n        for(int i=0; i<=sL; i++) {\n            \n            // j starts from 1, since dp[i][0] is false when i!=0;\n            for(int j=1; j<=pL; j++) {\n                char c = p.charAt(j-1);\n                \n                if(c != '*') {\n                    // The last character of s and p should match;\n                    // And, dp[i-1][j-1] is true;\n                    dp[i][j] = i>0 && dp[i-1][j-1] && (c=='?' || c==s.charAt(i-1));\n                }\n                else {\n                    // Two situations:\n                    // (1) '*' is the first character in p;\n                    // (2) For k>=0 and k<=i, there is some dp[k][j-1] being true;\n                    //     and '*' will match the rest sequence in s after index k;\n                    boolean flag = false;\n                    for(int k=i; k>=0; k--) { flag = dp[k][j-1]; if(flag) break;};\n                    \n                    dp[i][j] = j==1 || flag;\n                }\n            }\n        }\n        \n        return dp[sL][pL];\n    }\n\nBased on the same idea, I transposed the dp[][] matric and got the O(n^2) DP solution:\n\n    // O(n^2) DP solution with dp[][] matric transposed:\n    public boolean isMatch(String s, String p) {\n        int sL = s.length(), pL = p.length();\n        \n        boolean[][] dp = new boolean[pL+1][sL+1];\n        dp[0][0] = true;\n\n        for(int i=1; i<=pL; i++) {\n            boolean flag = false; // The flag is moved here;\n\n            for(int j=0; j<=sL; j++) {\n                flag = flag || dp[i-1][j];\n                char c = p.charAt(i-1);\n                \n                if(c != '*') {\n                    dp[i][j] = j>0 && dp[i-1][j-1] && (c=='?' || c==s.charAt(j-1));\n                }\n                else {\n                    // For k>=0 and k<=j, if any dp[i-1][k] is true,\n                    // then '*' will match the rest sequence in s after index k;\n                    dp[i][j] = i==1 || flag;\n                }\n            }\n        }\n        \n        return dp[pL][sL];\n    }
['Dynamic Programming', 'Java']