directory

• Write it first

• the title

• solution a

Second, the method

Method three,

• Write it first

So-called true warrior, dare to face to face with no API’s hand, I began to see the problem, most think it is to kill the topic, but I lived in flagrante delicto using Java regular expressions within API impulse, hand tore matching code, the ideas of the algorithm used is recursive, I start is to use the most direct recursion to solve this problem, When I looked at others’ solution later, I found that it was improved in recursion, using the idea of dynamic programming, which reduced the time cost of substring creation. I thought it was quite interesting, so I wrote it down. After all, I had never thought of implementing regular expressions myself, hahaha.

• the title

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. Note: s may be empty and contains 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 *. 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 Explanation: Because '*' stands for matching zero or more preceding elements, in this case the preceding element is 'a'. Thus, the string "aa" can be treated as 'a' repeated once. Example 3: input: s = "ab" p = ". * "output: true explanation:" * "said can match zero or more (' * ') any character ('. '). Example 4: Input: s = "aab" p = "c*a*b" Output: true Explanation: Because '*' means zero or more, here 'c' is zero and 'a' is repeated once. So it matches the string "aab". Example 5: Input: s = "Mississippi" p = "mis*is*p*." output: falseCopy the code

• solution a

In normal matching, we specify two special characters as rules: ‘. ‘, which means that any character can be matched, and ‘*’, which means that the character before it will be repeated 0-n times. So, except for these two special rule characters, everything else is a normal match. This may be easier said than done, but how do we implement special judgment for these two characters? Is very simple, as long as we match the normal character, continue to match except the substring can outside of this character, to do in the case of a special processing, when the characters are comparing the next character is *, if the two characters are equal, we only need to move the string, not moving rules of string, when don’t match, moving rules of string, and does not move and characters. This might sound dry, but I’m going to go straight to the code and add comments to the code.

    public static boolean isMatchS2(String s, String p) {
        //s is a string. P is a regular string
        // If the string and matching string are empty, the match is successful
        if(p.isEmpty()) return s.isEmpty();

        // If the string is not empty, the first character of the string is not empty
        // Is equal to the character of the rule string (note if the rule string is. Flase = flase = flase = flase = flase = flase = flase
        booleanflag = ! s.isEmpty() && (s.charAt(0) == p.charAt(0) || p.charAt(0) = ='. ');

        // After we get a flag indicating whether the first character is equal, we need to determine whether the next character of the rule string is equal
        If flag is flase, the first character does not match, so we just skip *
        / / line; When flag is true, that means the first match, we just move the string to the next one, and then match
        if(p.length() >= 2 && p.charAt(1) = =The '*') {// If one of the left and right sides is true, the match is successful
            return isMatchS2(s, p.substring(2)) || flag && isMatchS2(s.substring(1), p);
        }else{
            // If the rule string has no * and flag is true, just move the string and the rule string simultaneously
            return flag && isMatchS2(s.substring(1), p.substring(1)); }}Copy the code

Second, the method

This is not a very good solution, because in recursion, we pass in substrings every time, so we have to create a string to hold the substring in the next recursion, and that creates string creation overhead, so is there a way to reduce the overhead, or even get rid of it? Of course, we can use the idea of dynamic programming, we can open a two-dimensional array with two subscripts for strings and regular strings, and then we can pass in two strings instead of substrings when we recurse, But we need to recursively pass in two more subscripts of the current array. Let’s get right into the code and feel the magic of dynamic programming.

    public static boolean isMatchS3(String s, String p) {
        // This two-dimensional array is used to store the matching results of the corresponding subscripts, so that we encounter the same recursion
        // return the result directly.
        Boolean a[][] = new Boolean[s.length() + 1][p.length() + 1];
        // The recursive method is similar to the first method, but we pass the current array in the recursive method
        // Two subscripts (where the current two strings match)
        return match(a, 0.0, s, p);
    }

    public static boolean match(Boolean[][] a, int i, int j, String s, String p){
        // First judge the result in the two-dimensional array
        if(a[i][j] ! =null) return a[i][j];

        boolean ans;
        // Check if the rule string is complete, then check if the string is complete, and return true
        if(j == p.length()){
            ans = i == s.length();
        }else{
            // This is the core idea of recursion, similar to the above, except that the result is stored in a two-dimensional array
            boolean flag = i < s.length() && (s.charAt(i) == p.charAt(j) || p.charAt(j) == '. ');
            if(j + 1 < p.length() && p.charAt(j + 1) = =The '*'){
                ans = match(a, i, j + 2, s, p) || flag && match(a, i + 1, j, s, p);
            }else {
                ans = flag && match(a, i + 1, j + 1, s, p);
            }
        }
        a[i][j] = ans;
        return ans;
    }
Copy the code

Method three,

If you think recursion is a bit of a resource hog on the stack, you can just skip recursion and use non-recursion with dynamic programming, which actually takes more time to run than I’m going to say, poof ha ha ha. Let’s just go to the code

    public static boolean isMatchS4(String s, String p){
        boolean[][] datas = new boolean[s.length() + 1][p.length() + 1];
        datas[s.length()][p.length()] = true;
        for (int i = s.length(); i >= 0; i--) {
            for (int j = p.length() - 1; j >= 0; j--) {
                boolean firstMatch = i < s.length() && (p.charAt(j) == s.charAt(i) || p.charAt(j) == '.');
                if (j + 1 < p.length() && p.charAt(j + 1) == '*') {
                    datas[i][j] = datas[i][j + 2] || firstMatch && datas[i + 1][j];
                } else {
                    datas[i][j] = firstMatch && datas[i + 1][j + 1];
                }
            }
        }
        return datas[0][0];
    }
Copy the code