How to realize regular expression matching in C++

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.