10. Regular expression matching

Small knowledge, big challenge! This article is participating in the creation activity of “Essential Tips for Programmers”

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.

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 Thus, the string “aa” can be treated as ‘a’ repeated once. Example 3:

Input: s = “ab” p = “.” Output: true Description: “.” Can match zero or more (‘*’) characters (‘.’). Example 4:

Input: s = “aab” p = “CAB” Output: true Explanation: Since ‘*’ means zero or more, where ‘c’ is zero, ‘a’ is repeated once. So it matches the string “aab”. Example 5:

Input: s = “Mississippi” p = “misisp*.” output: false

Tip:

0 <= s.length <= 20
0 <= p.length <= 30
S may be empty and contain only lowercase letters from A to Z.
P may be empty and contains only lowercase letters from A to Z, as well as the characters. And *.
Ensure that each occurrence of the character * is preceded by a valid character

To define an array

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

Initialize the

Note:

“A *” can produce an empty string (that is, * can be used to delete the previous character), or several strings of a’s

So at initialization

Dp [0][I] represents the matching situation of p when S is an empty string. Only special cases such as A * A * a* a* can produce an empty string, so we can determine the length of the empty string by simply iterating over whether the even digits are consecutive *

State transition

p.charAt(j-1)==’.’||p.charAt(j-1)==s.charAt(i-1)

Dp [I][j]=dp[i-1][j-1]; dp[I][j]=dp[i-1];

p.charAt(j-1)==’*’

dp[i][j-2]

Before deleting because there is a function of the characters, so we try to delete one character at a time, before the observation can fit 2. P.c harAt (j, 2) = = s.c harAt (I – 1) | | p.c harAt (j, 2) = = ‘. ‘because that can produce several before with the * character of the same character, Therefore, if the current character of s is the same as the character before *, it means that if dp[i-1][j] can match, one more character will be generated to match the current character of S

code

class Solution {
    public boolean isMatch(String s, String p) {

        int n=s.length(),m=p.length();
        boolean[][] dp=new boolean[n+1][m+1];
        dp[0] [0] =true;
        for(int i=2; i<=m; i+=2)
        {
            if(p.charAt(i-1) = =The '*')
            {
                dp[0][i]=dp[0][i-2]; }}for(int i=1; i<=n; i++)for(int j=1; j<=m; j++) {if(p.charAt(j-1) = ='. '||p.charAt(j-1)==s.charAt(i-1))
                dp[i][j]=dp[i-1][j-1];
                else if(p.charAt(j-1) = =The '*')
                {
                    if(dp[i][j-2])
                       dp[i][j]=true;
                    else if(p.charAt(j-2)==s.charAt(i-1)||p.charAt(j-2) = ='. ')
                    {
                        dp[i][j]=dp[i-1][j]; }}}returndp[n][m]; }}Copy the code

10. Regular expression matching