When you see more text challenges in August, think again and continue to check LeetCode. Last time lasted no more than a few days was other trivia plan, I hope I can brush some topics this time. Last time, we’re on problem 10.
The title
Given a string s and a character rule P, implement a regular expression match that supports ‘.’ and ”. ‘.’ matches any single character.’ ‘matches zero or more of the preceding elements. The so-called match is to cover the entire string S, not parts of the string.
Example 1: Input: s = “aa” p = “a” Output: false Description: “A” cannot match the entire string “aa”.
Example 2: Input: s = “aa” p = “a*” Output: true Explanation: Because ‘*’ stands for matching zero or more preceding elements, in this case the preceding element is ‘a’. Thus, the string “aa” can be treated as ‘a’ repeated once.
Example 3: Input: s = “ab” p = “.” Output: true Description: “.” Indicates that zero or more characters (‘.’) can be matched.
Example 4: Input: s = “aab” p = “CAB” Output: true Explanation: Because ‘*’ means zero or more, here ‘c’ is zero and ‘a’ is repeated once. So it matches the string “aab”.
Example 5: Input: s = “Mississippi” p = “misisp*.” output: false
Train of thought
Although it was obviously a topic of dynamic programming, I did not come up with a solution at the beginning, so I referred to some online solutions. ‘.’ matches any character. The ” can match zero or more characters, but there is an implicit condition: the ” cannot appear alone, but must be paired with the preceding character to make sense. With this in mind, it is easy to try to summarize the state escape equation. First, state dp[I][j] is defined as the matching result of the first I characters of string s and the first j characters of string P. Note that I and j are not the subscript of string directly. The subscript of the ith character of the string is actually I +1. Dp [I][j] is the match between the first i-1 character of string s and the first j-1 character of string p. The reason is that you can’t express a string that’s empty, because subscript 0 is the first character. With states, the state transition equation follows:
Case 1: P [J-1]! = ‘*’
Child is 1: s] [I – 1 = = p [1] so dp [I] [j] = dp [I – 1] [1] child case 2: s [I – 1)! = p[j-1] then dp[I][j] = false
P [j-1] == ‘*’
In this case, p[j-2]p[j-1] as a whole because * can represent 0 matches, so at least dp[I][j] = dp[I][j-2] if 0 matches, it depends on s[I -1] is equal to p[j-2]; If they are not equal, they cannot match 1 or more times. If it’s equal, then after one match, this whole thing p[j-2]p[j-1] can still be used, because it’s the same thing 1 to n times.
Java version code
class Solution { public boolean isMatch(String s, String p) { int slen = s.length(); int plen = p.length(); // The default value is false Boolean dp[][] = new Boolean [slen + 1][plen + 1]; dp[0][0] = true; for (int i = 0; i <= slen; i++) { for (int j = 1; j <= plen; j++) { if (p.charAt(j-1) == '*') { dp[i][j] = dp[i][j-2]; if (i > 0 && matchChar(s.charAt(i-1), p.charAt(j-2))) { dp[i][j] = dp[i][j] || dp[i-1][j]; } } else { if (i > 0 && matchChar(s.charAt(i-1), p.charAt(j-1))) { dp[i][j] = dp[i-1][j-1]; } } } } return dp[slen][plen]; } private static boolean matchChar(char temp, char c) { if (c == '.') { return true; } if (temp == c) { return true; } return false; }}Copy the code