string.matches的复杂性是什么？

Question

一个示例代码,我尝试验证字符串是否是有效的整数

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

什么是时间复杂度matches？

Answer 1

这取决于正则表达式引擎的实现.假设没有真正的尴尬发生(例如,在这个正则表达式中不应该有回溯函数),我会说你的表达式产生的DFA会接受/拒绝O(n)中的任何字符串.

以下是Regexper表达式的描述:

请注意,没有办法说出一般正则表达式的复杂性.一些正则表达式需要回溯,你可以制作指数时间匹配的表达式.所以我的答案适用于这个特定的表达式,这个特定的表达式(实际上是任何特定的表达式)被编译成O(1)中的DFA.