CODEWITHSUNDEEP
javatime-complexity
JavaDeveloper
JavaDeveloper

Reputation: 5660

What is the complexity of string.matches?

A sample code, where I try to verify if the string is a valid interger

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

What is the time complexity of matches ?

Upvotes: 3

Views: 3946

Answers (2)

aioobe
aioobe

Reputation: 421170

That depends on the implementation of the regex engine. Assuming that nothing really awkward happens (there should be no backtracking involed in this regexp for example), I would say that the DFA resulting from your expression would accept/reject any string in O(n).

Here's a depiction of the expression from Regexper:

enter image description here

Note that there's no way to say what the complexity is for a general regexp. Some regexps require backtracking and you can craft expressions which take exponential time to match. So my answer applies to this particular expression, and this particular expression (any particular expression actually) is compiled into a DFA in O(1).

Upvotes: 5

dhalik
dhalik

Reputation: 465

Typically in a regex implementation a DFA is constructed when you construct the pattern, and then that DFA is used to match against the given string.

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

In terms of the complexity once you have a pattern pre compiled, you should approach the following complexity:

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

On mismatches (not a number), you can achieve anywhere between O(1) and O(m-1) time depending on where the pattern falls off the DFA.

If you are interested in how the DFA is created I suggest you watch this video. I found it helpful when learning:

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

Upvotes: 0

Related Questions