Nuggets team number online, help you Offer impromptu! Click to view spring recruitment positions in big factories

I. Title Description:

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).Copy the code

A match is successful only if the two strings match exactly.

Description:

  • S may be empty and contain only lowercase letters from A to Z.
  • P may be empty and contain only lowercase letters from A to Z, as well as characters? And *.

Example 1:

Input: s = "aa" p = "a" Output: false Description: "A" cannot match the entire string "aa".Copy the code

Example 2:

Input: s = "aa" p = "*" Output: true Description: '*' can match any string.Copy the code

Example 3:

Enter: s = "cb" p = "? A "output: false Explanation: '? 'matches 'c', but the second 'a' does not match 'b'.Copy the code

Example 4:

Input: s = "adceb" p = "*a*b" Output: true Explanation: The first '*' matches the empty string and the second '*' matches the string "dCE ".Copy the code

Example 5:

Input: s = "acdcb" p = "a*c? B "output: falseCopy the code

Subject address: leetcode-cn.com/problems/wi…

Ii. Analysis of Ideas:

10. Regular Expression Matching

We started off with the same idea we had on problem 10, recursion. If the current character is matched successfully, the final result is whether subsequent characters are matched successfully.

But I ran out of time. I’m going to have to do dynamic programming.

Define a two-dimensional state array Boolean dpArray[s.length()+1][p.length()+1]

Dp [I][j] indicates whether the first I characters of S match the first j characters of P.

We define dpArray[0][0] = true to indicate that s = “” and p = “” are matched successfully.

Define the state transition equation: Assuming we know the value of dpArray[0…i-1][0…j-1], then we can derive the value of dpArray[I][j]

  • whenp[j] = "*"There are three cases:
1. P [j] = "*" 1. DpArray [I][j] = dpArray[I][j-1] If s[I] and p[j-1] match, then s[I] and p[j] also match s = abcd p = ab* CD I = 1, J = 2 dpArray[1][1] = dpArray[1][1] = dpArray[1][1] If s[i-1] and p[j-1] match, then s[I] and p[j] match, s = abcd p = ab*d I = 2, DpArray [1] = dpArray[2] = dpArray[1] = dpArray[1] = dpArray[2] = dpArray[1] = dpArray[1] If s[i-1] matches p[j], then s[I] and p[j] match s = abcd p = a*d I = 2, j = 2 dpArray[2][1] = dpArray[1]Copy the code
  • whenp[j] = "?"
"?" If s[i-1] matches p[j-1], then s[I] matches p[j]Copy the code
  • whenp[j] = "a-z"
DpArray [I] [j] = dpArray [I - 1] [1] [I] && s = = p [j] explain: If s[i-1] and p[j-1] match and s[I] == p[j], then s[I] and p[j] also match. Let's take s = abcd, p = a*d "" A *d "" T F F F F A F T T F B F F T F C F F T F d F F T T T write the array a few times and you'll get the idea.Copy the code

Dp [s.length()][p.length()] is the final answer

Iii. AC Code:

private static boolean dfs(String s, String p, int sIndex, Int pIndex) {if (pIndex == p.length()) {return true; if (pIndex == p.length()) {return true; } return sIndex == s.length(); If (sIndex == s.length()) {int I = pIndex; i < p.length(); i++) { if ('*' ! = p.charAt(i)) { return false; } } return true; } if ('*' == p.charAt(pIndex)) { boolean flag = false; for (int i = sIndex; i < s.length(); i++) { flag = dfs(s, p, i, pIndex + 1); if (flag) { break; } } return flag; } if ('? ' == p.charAt(pIndex)) { return dfs(s, p, sIndex + 1, pIndex + 1); } if (s.charAt(sIndex) == p.charAt(pIndex)) { return dfs(s, p, sIndex + 1, pIndex + 1); } else { return false; } } public static boolean isMatch(String s, String p) { boolean[][] dpArray = new boolean[s.length() + 1][p.length() + 1]; dpArray[0][0] = true; S = ABC, p = *****c for (int I = 0; i < p.length(); i++) { if ('*' == p.charAt(i)) { dpArray[0][i + 1] = true; } else { break; } } for (int i = 0; i < s.length(); i++) { for (int j = 0; j < p.length(); j++) { if ('*' == p.charAt(j)) { dpArray[i + 1][j + 1] = dpArray[i][j] || dpArray[i][j + 1] || dpArray[i + 1][j]; } else if ('? ' == p.charAt(j)) { dpArray[i + 1][j + 1] = dpArray[i][j]; } else { dpArray[i + 1][j + 1] = (s.charAt(i) == p.charAt(j)) && dpArray[i][j]; } } } return dpArray[s.length()][p.length()]; }Copy the code

Iv. Summary:

I think this is the easiest solution to understand, and if you want to optimize, you can use a greedy algorithm to deal with asterisks. Even better AC automata. But it’s a lot harder to understand.