java 13ms dp solution with explanation
This problem is simliar to 10. Regular Expression Matching. The difference lies in how the * works. In the previous problem, * can only matches zero or more of 
This problem is simliar to [10. Regular Expression Matching](https://leetcode.com/problems/regular-expression-matching/). The difference lies in how the ```*``` works. In the previous problem, ```*``` can only matches zero or more of its preceding element. In this problem, ```*``` can match any sequence (including empty sequence). \nOf course, both the problems can be solved with DP, and the key is how we process ```*```.  In the previous problem, a* can be decoded as zero ```a```, one ```a``` or more ```a```. Similarly, in this problem, ```*``` can be decoded as empty sequence, one character or more character. \nHere, we use a two demension array to denote whether substrings of ```s``` and ```p``` match. ```match[i][j]``` denotes whether ```s.substring(0, i)``` and ```p.substring(0, j)``` matches. If ```p.charAt(j)``` is not ```*```, we judge whether ```p.charAt(j)``` and ```s.charAt(i)``` matches. If ```p.charAt(j)``` is ```*```, then there could be three conditions:\n1. ```match[i][j] = match[i][j - 1]```, i.e., ```*``` is decoded as empty sequence\n2. ```match[i][j] = match[i - 1][j - 1]```, i.e., ```*``` is decoded as one character\n3. ```match[i][j] = match[i - 1][j]```, i.e., ```*``` is decoded as more than one character\n```\npublic boolean isMatch(String s, String p) {\n\tboolean match[][] = new boolean[s.length() + 1][p.length() + 1];\n\tmatch[0][0] = true;\n\tfor (int i = 0; i < p.length(); i++) // judge whether the substring of p matchese empty sequence\n\t\tif (p.charAt(i) == \'*\')\n\t\t\tmatch[0][i + 1] = match[0][i];\n\tfor (int i = 0; i < s.length(); i++)\n\t\tfor (int j = 0; j < p.length(); j++) {\n\t\t\tif( p.charAt(j) == \'*\' )\n\t\t\t\tmatch[i + 1][j + 1] = (match[i][j + 1] | match[i + 1][j] | match[i][j]);\n\t\t\telse if( s.charAt(i) == p.charAt(j) || p.charAt(j) == \'?\' )\n\t\t\t\tmatch[i + 1][j + 1] = match[i][j];\n\t\t}\n\treturn match[s.length()][p.length()];\n}\n```
['Dynamic Programming', 'Java']