This article is participating in the “Java Theme Month – Java Brush questions punch card”, see the activity link for details

preface

The regular expression match of question 10 is as follows:

Given a string s and a character rule P, implement a regular expression match that supports ‘.’ and ‘*’.

  • '. 'Matches any single character
  • The '*'Matches zero or more of the preceding elements

By matching, you want to cover the entire string S, not parts of the string.

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”.

First of all, I did not solve this question qaq, the following answers are from the buckle. Did not think of using dynamic programming, leaving no technical tears 🤦♂️~

A, thinking

Matching string S with the regular expression P is a step-by-step matching process, each time a character or combination of characters (such as character + asterisk) from P is matched in S.

There are two cases:

  • pMatches a character insA character in
  • pMatches the character combination insMultiple characters in

We can enumerate matches using dynamic programming

Define dp[I][j] to indicate whether the first I characters in s match the first j characters in p

When enumerating an equation of state, note that the ‘*’ represents zero or more elements that match the p[i-1] that precedes it, in two cases

  • p[i-1] ! = s[j] 则 dp[i][j] = dp[i][j-2], such ass = 'abc' p = 'abcd*'At this time,'d*'You can view it as zero matches
  • p[i-1] == s[j] || p[i-1] = '.' , need to considerThe '*'The preceding character has been matched several times

To sum up, the state transition equation is as follows:

Matches (x, y) for x and y matches, namely, y = = x | | y = = ‘. ‘

Second, the implementation

Code implementation

Variable description: DP [][] : two-dimensional array records whether the first I characters in S match the first J characters in P

    public boolean isMatch(String s, String p) {
            int m = s.length();
            int n = p.length();

            // A two-dimensional array to record the state
            boolean[][] dp = new boolean[m + 1][n + 1];
            dp[0] [0] = true;
            for (int i = 0; i <= m; ++i) {
                for (int j = 1; j <= n; ++j) {
                    // Special case *
                    if (p.charAt(j - 1) = =The '*') {
                        dp[i][j] = dp[i][j - 2];
                        if(i ! =0 && matches(s.charAt(i-1), p.charAt(j-2))) {
                            dp[i][j] = dp[i][j] || dp[i - 1][j]; }}else {
                        if(i ! =0 && matches(s.charAt(i-1), p.charAt(j-1))) {
                            dp[i][j] = dp[i - 1][j - 1]; }}}}return dp[m][n];
        }

        public boolean matches(char x, char y) {
            if (y == '. ') {
                return true;
            }
            return x == y;
        }
Copy the code

The execution result

Third, summary

Today is the 10th question of the buckle ~ this series will update the 1-10 questions of the buckle for 10 consecutive days! Dig gold coin, I come 😁