[C++] Clean and concise bottom-up dp code with detailed explanation, easy to understand.
This question is similar to 10. Regular Expression Matching, and both question can be solved using dynamic programming.\n\nFirst, we need to create a 2d dp tabl
This question is similar to [10. Regular Expression Matching](https://leetcode.com/problems/regular-expression-matching/), and both question can be solved using dynamic programming.\n\nFirst, we need to create a 2d dp table `dp`. The size of this table is `(s.size() + 1) * (p.size() + 1)`. We introduce `+1` here to better handle the edge cases where we have an empty string or an empty pattern. `dp[i][j]` means whether the substring from index `0` to `i - 1` of the original string `s` matches with the subpattern from index `0` to `j - 1` of the original pattern `p`.\n\nNext, we initialize the base cases. There are three base cases:\n1. **When both the string and the pattern are empty.**\n\tAlways match. `dp[0][0] = true;`\n2. **When only the string is empty.**\n\tOnly if the subpattern only consists of  `*`, we have a match. \n3. **When only the pattern is empty.**\n\tAlways not match.\n\t\nThere are two special characters that we need to take special care in the pattern.\n1. `?`\n\tThis is actually easy to deal with. Everytime when we encounter this, we can consider it matches with any character in the string. Say we are currently at `dp[i][j]`, and we have `p[j - 1] == \'?\'`, then we know it matches with `s[i - 1]`, no matter what `s[i - 1]` actually is.\n2. `*`\n\tThis is slightly hard to deal with. A small technique while dealing this kind of question is to actually draw out the dp table, and try to fill out the table manually, when the state transfer function is not very straightforward. Everything will become much clearer after you fill out one row or two.\n\tWhen we encounter a `*` in the pattern, and assuming that we\'re currently trying to figure out what `dp[i][j]` is. Then we need to consider two cases if `p[j - 1] == \'*\'`.\n\t1. **Is `dp[i - 1][j]` true?**\n\t\tIf yes, it means the current subpattern `p[0...j - 1]` we have matches the substring `s[0... i - 2]`. Then will `p[0...j - 1]` match with `s[0... i - 1]`? The answer is yes, because `*` can match any sequence of characters, so it\'s able to match one more character `s[i - 1]`.\n\t2. **Is `dp[i][j - 1]` true?**\n\t\tIf yes, it just means the current substring `s[0...i - 1]` matches with the subpattern `p[0...j - 2]`. Therefore, if we add one more `*` into the subpattern, it will also match as `*` can match empty subsequence.\n\t\t\n\n##### O(mn) space\n**Note**: `m` means the size of the string, `n` means the size of the pattern.\n```cpp\nclass Solution {\npublic:\n    bool isMatch(string s, string p) {\n        vector<vector<bool>> dp(s.size() + 1, vector(p.size() + 1, false));\n        dp[0][0] = true;\n        for (int j = 0; j < p.size() && p[j] == \'*\'; ++j) {\n            dp[0][j + 1] = true;\n        }\n        \n        for (int i = 1; i <= s.size(); ++i) {\n            for (int j = 1; j <= p.size(); ++j) {\n                if (p[j - 1] == \'*\') {\n                    dp[i][j] = dp[i - 1][j] || dp[i][j - 1];\n                } else {\n                    dp[i][j] = (s[i - 1] == p[j - 1] || p[j - 1] == \'?\') && dp[i - 1][j - 1];\n                }\n            }\n        }\n\n        return dp[s.size()][p.size()];\n    }\n};\n```\n\n##### O(n) space\nWe can also use 1d table to solve this problem, but the code will be less readable.\n**Note**: `n` means the size of the pattern.\n```cpp\nclass Solution {\npublic:\n    bool isMatch(string s, string p) {\n        vector<bool> dp(p.size() + 1, false);\n        dp[0] = true;\n        for (int j = 0; j < p.size() && p[j] == \'*\'; ++j) {\n            dp[j + 1] = true;\n        }\n        \n        for (int i = 1; i <= s.size(); ++i) {\n            dp[0] = false;\n            bool neighborLastRow = i == 1;\n            for (int j = 1; j <= p.size(); ++j) {\n                bool currLastRow = dp[j];\n                if (p[j - 1] == \'*\') {\n                    dp[j] = currLastRow || dp[j - 1];\n                } else {\n                    dp[j] = (s[i - 1] == p[j - 1] || p[j - 1] == \'?\') && neighborLastRow;\n                }\n                neighborLastRow = currLastRow;\n            }\n        }\n\n        return dp[p.size()];\n    }\n};\n```
['Dynamic Programming', 'C++']