Clever Geek Handbook

What is the complexity of string.matches?

Sample code where I am trying to check if a string is a valid firewall

 public static boolean isValidNumberUsingRegex(String num) {
        return num.matches("[-+]?\\d+(\\.\\d+)?");
    }

What is the time complexity matches

?

+3


source to share


2 answers


It depends on the implementation of the regex engine. Assuming nothing really awkward is happening (there should be no backtracking in this regex), I would say that the DFA you get from your expression will accept / reject any string in O (n).

Here's an expression from Regexper:



enter image description here

Note that there is no way to tell what complexity is for a generic regex. Some regexes require backtracking and you can create expressions that must match exponential time. So my answer is for this particular expression, and that particular expression (any particular expression in fact) is compiled to DFA in O (1).

+5


source


Typically in a regex implementation, a DFA is created when the template is created, and then the DFA is used to match against the given string.

If you keep the method as it is, it will probably be near O (n * m), where n is the length of the template and m is the length of the string, since the DFA will need to be built each time. On the other hand, if you use the Pattern class to precompile the DFA, you can achieve much better results.

In terms of complexity, when you have a pre-compiled template, you should approach the following complexity:

In matches, this will take at least O (m) time, where m is the length of the string



In case of mismatches (not numbers), you can reach anywhere between O (1) and O (m-1) times depending on where the pattern falls from the DFA.

If you are interested in how DFA is created, I suggest you watch this video. I found this helpful when teaching:

https://www.youtube.com/watch?v=dlH2pIndNrU

0


source






More articles:


All Articles