I had a lot of work to do last week, so I did not insist on continuing to brush Leetcode. I will continue to work on one problem when I am free today.
The title
Given a string (s) and a character pattern (p), implement a system that supports ‘? The wildcard of ‘and ‘*’ matches.
‘? ‘can match any single character. ‘*’ can match any string (including empty strings). A match is successful only if the two strings match exactly.
Description:
sMay be empty and contains only froma-zLowercase letters.pMay be empty and contains only froma-zLowercase letters, as well as characters?和*.
Example 1: Input: s = “aa” p = “a” Output: false Description: “A” cannot match the entire string “aa”.
Example 2: Input: s = “aa” p = “” Output: true Explanation: “can match any string.
Example 3: Enter: s = “cb” p = “? A “output: false Explanation: ‘? ‘matches ‘c’, but the second ‘a’ does not match ‘b’.
Example 4: Input: s = “adceb” p = “ab” Output: true Explanation: The first ” matches the empty string and the second ” matches the string “dCE “.
Example 5: Enter: s = “acdcb” p = “a*c? B “output: false
Train of thought
This is also dynamic programming, and we actually did a similar problem before. The key to leetcode-regular expression matching is to define the state and find the transition equation of state transition, which I think is more by experience, many people are confused about dynamic planning point is that they do not know how to define the state, and if they have not encountered, it is difficult to think of how to define the state. Dp [slen+1][plen+1], dp[I][j] means that the first I bit of S can match the first j bit of P. The reason why the length is increased by 1 is to consider the case where the length is 0. Next we are divided into two cases to discuss, as a whole, first divided into two: and not. This is because the length that can be represented is variable, not necessarily only represents 1 bit, even if it is matched ‘? ‘. If s[i-1] cannot match p[j-1], then dp[I][j] = false; if s[i-1] cannot match p[j-1], then dp[I][j] = false; If S [i-1] matches p[j-1], then dp[I][j] = dp[i-1][J-1]. What about if it is, because you can match 0 to n, so dp [I] [j] = dp [0] [1] | | dp […]. [j – 1) | | dp [I] [1]. The last space of s, the last 1, the last 2 bits… The last I bit. The schematic diagram is as follows:
Another constant optimization here is that if true is encountered, there is no need to do the goods operation later, because the result must be true.
Java version code
class Solution { public boolean isMatch(String s, String p) { int slen = s.length(); int plen = p.length(); Boolean [][] dp = new Boolean [slen+1][plen+1]; // dp[I +1][j+1] = 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.c harAt (j - 1) = = '*') {/ / can match 0 - any long string, so is the dp [0] I [1] int k = 0; while (k <= i) { if (dp[i][j]) { break; } dp[i][j] = dp[i][j] || dp[k][j-1]; k++; } } else { if (i > 0 && matchChar44(s.charAt(i-1), p.charAt(j-1))) { dp[i][j] = dp[i-1][j-1]; } } } } return dp[slen][plen]; } /** * * @param temp * @param c * @return */ private static boolean matchChar44(char temp, char c) { if (c == '? ') { return true; } if (temp == c) { return true; } return false; }}Copy the code