# Regular Expression Matching Given an input string (`s`) and a pattern (`p`), implement regular expression matching with support for`'.'`and`'*'`. ``` '.' Matches any single character. '*' Matches zero or more of the preceding element. ``` The matching should cover the **entire** input string (not partial). **Note:** * `s` could be empty and contains only lowercase letters `a-z`. * `p` could be empty and contains only lowercase letters `a-z`, and characters like `.` or `*`. **Example 1:** ``` Input: s = "aa" p = "a" Output: false Explanation: "a" does not match the entire string "aa". ``` **Example 2:** ``` Input: s = "aa" p = "a*" Output: true Explanation: '*' means zero or more of the precedeng element, 'a'. Therefore, by repeating 'a' once, it becomes "aa". ``` **Example 3:** ``` Input: s = "ab" p = ".*" Output: true Explanation: ".*" means "zero or more (*) of any character (.)". ``` **Example 4:** ``` Input: s = "aab" p = "c*a*b" Output: true Explanation: c can be repeated 0 times, a can be repeated 1 time. Therefore it matches "aab". ``` **Example 5:** ``` Input: s = "mississippi" p = "mis*is*p*." Output: false ``` ## Analysis Two string / array comparison, and it has subproblems that could lead to Dynamic Programming solution. `isMatch(char[] str, char[] pattern)` **State:** `dp[i][j]` Defined as `new boolean[str.length + 1][pattern.length + 1]` The first `i` characters in the `str[]` matches first `j` characters in `pattern[]` Note: the corresponding index (subscript) will be `i - 1` in `str[]`, `j - 1` in `pattern[]` **Initialization:** Assumption: `'*'` will never be the first character `dp[0][0] = true` - no chars chosen from either of the string / char array, should match then for `dp[0][i]` (for `a*` case): ```java for (int i = 1; i <= pattern.length; i++) { if (pattern[i-1] == '*') { dp[0][i] = dp[0][i-2]; } } ``` **State Transfer Function:** 1. if `p.charAt(j) == s.charAt(i)` : `dp[i][j] = dp[i-1][j-1]` 2. if `p.charAt(j) == '.'`: `dp[i][j] = dp[i - 1][j-1]` 3. if `p.charAt(j) == '*'` : sub conditions 1. if `p.charAt(j-1) != s.charAt(i)` : `dp[i][j] = dp[i][j-2]` // in this case, `a*` only counts as empty 2. if `p.charAt(j-1) == s.charAt(i)` or `p.charAt(j - 1) == '.'`: 1. `dp[i][j]= dp[i-1][j]` // in this case, `a*` counts as multiple `a` 2. (*REDUNDANT*) or `dp[i][j] = dp[i][j-1]` // in this case, `a*` counts as single `a` 3. or `dp[i][j] = dp[i][j-2]` // in this case, `a*` counts as empty **Answer:** `dp[m][n]` 另：中文解释 From [@caiconghuai GitHub](https://github.com/caiconghuai/leetcode/tree/master/topics/Dynamic%20Programming/010.%20Regular%20Expression%20Matching): > 在正则表达式中，由于不同的字符会有不同的匹配规则，其中`.`和`*`比较特别，需要对这两类字符进行分类讨论。 > > * **定义状态** > > `dp[i][j]` - 表示输入串长度为i，模式串长度为j时，是否能匹配。 > * **初始化状态值**： > * 输入串为空，模式串为空：`dp[0][0]` 必然可以匹配，即 `dp[0][0]=true` > * 输入串非空，模式串为空：由于模式串为空，此时必然不可匹配，即`dp[i][0]=false,` `i > 0` > * 输入串为空，模式串非空：此时如果模式串中有`*`，则是可以匹配0个前面的字符的，所有我们通过条件 `p.charAt(j-1) == '*' && dp[0][j-2]` 来判断是否可匹配 > * **转移方程**，转移方程表示通过已知的状态值来求解未知的状态值，在这里就是我们要求解 > > `dp[i][j]`，但是对于所有长度小于`i`的输入串和长度小于`j`的模式串，我们已知其匹配情况。现在，我们怎么利用前面的信息，来得到`dp[i][j]`的值。我们首先需要分析模式串的当前字符来做判断: > > * `p.charAt(j-1) == s.charAt(i-1)`当前模式串字符一样，可以将当前字符匹配掉，然后状态转化如下: `dp[i][j] = dp[i-1][j-1];` > * `p.charAt(j-1) == '.'`当前模式串字符为`.`，可以匹配任意的字符，可以将当前输入串字符匹配掉，然后状态转化为:`dp[i][j] = dp[i-1][j-1]` > * `p.charAt(j-1) == '*'`由于`*`可以匹配0个或多个它的上一个字符，所以根据上一个字符的不同还需要做不同的分析： > * `p.charAt(j-2) != s.charAt(i-1) && p.charAt(j-2) != '.'`，这种情况说明上一个字符即不是`.`，也不和输入串的当前字符一样，所有无法用一个或多个上一个字符对输入串进行匹配，此时`*`只能匹配0个上一个字符: `dp[i][j] = dp[i][j-2];` > * 如果是这个条件里，说明上一个字符和输入串的当前字符是可以进行匹配的，故此时`*`即可以匹配0个前一个字符，也可以匹配1个前一个字符，也可以匹配多个前一个字符: `dp[i][j] = (dp[i][j-1] || dp[i-1][j] || dp[i][j-2])` Note: 这种情况，也可以用`dp[i][j] = (dp[i-1][j] || dp[i][j-2])` ## Solution **DP Solution (12ms 97% AC)** ```java class Solution { public boolean isMatch(String s, String p) { char[] text = s.toCharArray(); char[] pattern = p.toCharArray(); int m = text.length; int n = pattern.length; boolean dp[][] = new boolean[m + 1][n + 1]; dp[0][0] = true; // Deals with patterns like a* or a*b* or a*b*c* for (int i = 1; i < n + 1; i++) { // Assumption: '*' will never be the first character if (pattern[i-1] == '*') { dp[0][i] = dp[0][i - 2]; } } for (int i = 1; i < m + 1; i++) { for (int j = 1; j < n + 1; j++) { if (pattern[j - 1] == '.' || pattern[j - 1] == text[i - 1]) { dp[i][j] = dp[i-1][j-1]; } else if (pattern[j - 1] == '*') { dp[i][j] = dp[i][j - 2]; if (pattern[j-2] == '.' || pattern[j - 2] == text[i - 1]) { dp[i][j] = dp[i][j] | dp[i - 1][j]; } } else { dp[i][j] = false; } } } return dp[m][n]; } } ``` DP - Reference ```java class Solution { //dp[i][j] first ith characters match jth characters // abc // ab. // ab* //initial dp[0][0] = true; dp[][0] = false; public boolean isMatch(String s, String p) { if(s == null || p == null){ return false; } boolean[][] dp = new boolean[s.length() +1 ][p.length() + 1]; for(int i = 0; i <= s.length(); i++){ for(int j = 0;j <= p.length(); j++){ if(i == 0 && j == 0){ dp[i][j] = true; continue; //这个地方不能少了continue } if(j == 0){ dp[i][j] = false; continue;//contiue不能少了 } //dp[i][j] = false; // 默认false 不能没了 if(p.charAt(j - 1) != '*'){ if(i > 0 && (p.charAt(j-1) == '.' || p.charAt(j-1) == s.charAt(i-1))) dp[i][j] |= dp[i-1][j-1]; } else{ if(j > 1) dp[i][j] |= dp[i][j-2]; if(i > 0 && (p.charAt(j-2) == '.' || s.charAt(i-1) == p.charAt(j-2))){ dp[i][j] |= dp[i-1][j]; } } } } return dp[s.length()][p.length()]; } } ``` ## Reference [https://github.com/caiconghuai/leetcode/tree/master/topics/Dynamic Programming/010. Regular Expression Matching](https://github.com/caiconghuai/leetcode/tree/master/topics/Dynamic%20Programming/010.%20Regular%20Expression%20Matching)