Regular Expression Matching


  • 0

    Click here to see the full article post


  • 0
    P

    Recursive solution fails for the following:
    String text = "daba";
    String pattern = "*a";


  • 0
    P

    Please ignore

    Recursive solution fails for the following:
    String text = "daba";
    String pattern = "*a";


  • 0
    B

    @payamrastogi *a is not a valid regex pattern. If anything the solution is simply not validating that the pattern is a correct regex pattern well enough.


  • 0
    C

    why text = "abb" pattern = ".*d" is false?


  • 0
    B

    @chenlinfeng Cuz ".*" matches "abb", but "d" matches nothing in the text, thus false.


  • 0
    C
    This post is deleted!

  • 0
    N

    @BeeFarmer, why text = "aab" pattern = "cab" is true? "c" matches nothing in the text.


  • 0
    N

    I mean "cab".


  • 0
    N

    I understood. @BeeFarmer, pls ignore me.


  • 0
    A

    You do not need space for recursion. You do not need to copy any strings. Just pass pointers/indices. Old Java versions even had Substring that did not allocate any new memory.


  • 0

    @Ark-kun The time/space complexity discussed is based on the solution presented. Recursions more similar to Approach #2 can of course save space by manipulating indices instead.


  • 0
    C

    When string = "ab" and pattern = ".*c", the testcase failed in recursive version.
    It may cause out of bound exception while trying to substring an empty string.
    We may need to add empty check in the code.
    Here's my modified version.

    class Solution {
        public boolean isMatch(String s, String p) {
            if (p.isEmpty()) return s.isEmpty();
            boolean firstMatch = (!s.isEmpty() &&
                                   (p.charAt(0) == s.charAt(0)) || p.charAt(0) == '.');
            
            if (p.length() >= 2 && p.charAt(1) == '*') {
                return (isMatch(s, p.substring(2)) || firstMatch && !s.isEmpty() && isMatch(s.substring(1), p));
            } else {
                return firstMatch && !s.isEmpty() && isMatch(s.substring(1), p.substring(1));
            }
        }
    }
    

  • 0
    X

    @charles.cp.tsai
    But the firstMatch has checked it, right?


  • 0

    @charles.cp.tsai The test case "ab", ".*c" passes successfully when I ran it. firstMatch will check that text is nonempty, so text.substring(1) is defined. The check of pattern.length() >= 2 will ensure pattern.substring(2) is defined.


  • 0
    C

    @xiaoyanghaitao @awice I found the problem in my code...

    the firstMatch should be

    boolean firstMatch = (!s.isEmpty() &&
                                   (p.charAt(0) == s.charAt(0) || p.charAt(0) == '.'));
    

    not

    boolean firstMatch = (!s.isEmpty() &&
                                   (p.charAt(0) == s.charAt(0)) || p.charAt(0) == '.');
    

    Thanks guys' clarification :)


  • 0
    A

    javascript:

    var isMatch = function(s, p) {
        return (new RegExp("^"+p+"$")).test(s);
    };
    

  • 0
    H

    Approach #1 fails in Python3 for "aaaaaaaaaaaaab" "aaaaaaaaaac" because of Time Limit Exceeded

    I have made an optiomisation by simplifying the pattern (just remove all the * (a*.* = .) close to the . and then remove duplicated * (aa* = a*))

    def simplifyRegexp(self, p):
        pointer = 0
        while (pointer < len(p)-1):
            if (p[pointer] == "." and p[pointer+1] == "*"):
                while ((pointer+3) < len(p) and p[pointer+3] == "*"):
                    p = p[:pointer+2] + p[pointer+4:]
                begin = pointer
                while ((begin) > 0 and p[begin-1] == "*"):
                    begin -= 2
                p = p[:begin] + p[pointer:]
            pointer += 1
        pointer = 0
        while (pointer < len(p)-1):
            if (p[pointer+1] == "*"):
                while ((pointer+3) < len(p) and p[pointer+3] == "*" and p[pointer+2] == p[pointer]):
                    p = p[:pointer+2] + p[pointer+4:]
            pointer += 1
        return p
    

    This is not fuly optimise but at least it passes.


  • 0
    L

    Why does the top-down recursive approach need memoization? I cannot think of an example input that would require repeated work. Can anyone give an example?


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.