Shulou(Shulou.com)05/31 Report--

Most people do not understand the knowledge points of this "C++ how to achieve regular expression matching" article, so the editor summarizes the following, detailed contents, clear steps, and has a certain reference value. I hope you can get something after reading this article, let's take a look at this "C++ how to achieve regular expression matching" article.

Regular Expression Matching 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 Murz.

P could be empty and contains only lowercase letters a Murz, 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

This regular expression matching problem is very similar to that Wildcard Matching problem, except that the meaning of * is different. In the previous question, * means that any number of characters can be replaced, while the * in this question means that the previous character can have 0, 1 or more characters, that is, the string aqb can represent b or aaab, that is, the number of an is arbitrary, and this problem is more difficult than the previous one. The sub-situation is more complicated and needs to be solved by recursive Recursion. The general idea is as follows:

-if p is empty, and s is also empty, return true, and vice versa, return false.

-if the length of p is 1, the length of s is also 1, and it is the same or p is "." Then true is returned, and false is returned otherwise.

-if the second character of p is not *, return false if s is empty, otherwise determine whether the first character matches, and call the recursive function to match from the second character.

-if the second character of p is *, perform the following loop, provided that if s is not empty and the first character matches (including p [0] as a dot), the recursive function is called to match s and the p of the first two characters is removed (this is because it is assumed that the asterisk at this time is used to make the previous character appear 0 times to verify whether it matches), and if the match returns true, otherwise s removes the first letter (because the first letter matches at this time We can remove the initials of s, and p can have any initials because of the asterisk, so we don't need to remove it.), continue the loop.

-return the result of calling the recursive function to match s and remove the p of the first two characters. (the reason for this is to deal with things that cannot be matched by asterisks, such as s = "ab", p = "axib". After entering the while loop, we find that "ab" and "b" do not match, so s becomes "b". After jumping out of the loop, we go to the final return to compare "b" and "b". Return to true. Another example, such as s = "", p = "a *", because s is empty, will not enter any if and while, can only be compared to the final return, return true, correct).

Solution 1:

Class Solution {public: bool isMatch (string s, string p) {if (p.empty ()) return s.empty (); if (p.size () = = 1) {return (s.size () = = 1 & & (s [0] = = p [0] | | p [0] = = ".")) } if (p [1]! = "*") {if (s.empty ()) return false; return (s [0] = = p [0] | | p [0] = = ".") & & isMatch (s.substr (1), p.substr (1)) } while (! s.empty () & (s [0] = = p [0] | | p [0] = = ".") {if (isMatch (s, p.substr (2) return true; s = s.substr (1);} return isMatch (s, p.substr (2));}}

The above method can be written more succinctly, but the whole idea is still the same. first, determine whether p is empty or not. if it is empty, return the result according to the empty of s. When the second character of p is the * sign, because the number of characters before the * sign can be arbitrary and can be 0, then we first use recursion to call 0, that is, to remove and compare the two characters directly, or when s is not empty and the first character is the same as the first character of p, then call recursion on s and p without the first character. Note that p cannot remove the first character. Because there can be unlimited characters before the * sign. If the second character is not a * sign, then honestly compare the first character, and then call recursion on the following string, as shown in the code below:

Solution 2:

Class Solution {public: bool isMatch (string s, string p) {if (p.empty ()) return s.empty (); if (p.size () > 1 & & p [1] = = "*") {return isMatch (s, p.substr (2)) | (! s.empty () & (s [0] = = p [0] | | p [0] = ".") & isMatch (s.substr (1), p)) } else {return! s.empty () & & (s [0] = = p [0] | | p [0] = = ".") & & isMatch (s.substr (1), p.substr (1));}

We can also use DP to define a two-dimensional DP array, where dp [I] [j] denotes whether s [0memi) and p [0memj) are match, and then there are three cases (the following part is extracted from this post):

1. P [I] [j] = P [I-1] [j-1], if p [j-1]! = "*" & (s [I-1] = = p [j-1] | | p [j-1] = ".")

2. P [I] [j] = P [I] [j-2], if p [j-1] = = "*" and the pattern repeats for 0 times

3. P [I] [j] = P [I-1] [j] & & (s [I-1] = = p [j-2] | | p [j-2] = = "."), if p [j-1] = "*" and the pattern repeats for at least 1 times.

Solution 3:

Class Solution {public: bool isMatch (string s, string p) {int m = s.size (), n = p.size (); vector dp (m + 1, vector (n + 1, false)); dp [0] [0] = true; for (int I = 0; I 0 & (s [I-1] = = p [j-2] | | p [j-2] = ".") & dp [I-1] [j]) } else {dp [I] [j] = I > 0 & & dp [I-1] [j-1] & & (s [I-1] = = p [j-1] | | p [j-1] = = ".");} return dp [m] [n];} The above is about the content of this article on "how to achieve regular expression matching in C++". I believe we all have some understanding. I hope the content shared by the editor will be helpful to you. If you want to know more about it, please follow the industry information channel.

Welcome to subscribe "Shulou Technology Information " to get latest news, interesting things and hot topics in the IT industry, and controls the hottest and latest Internet news, technology news and IT industry trends.