下述Python示例代码中正则表达式（Regex）方法的时间复杂度是多少？

Question: #

What is the time complexity of the regex method in the following Python sample code?

import re
for _ in range(int(input())):
    s=input() # 输入字母数字字符串
    print(sum(map(int,re.findall('\d+',s))))

Answer: #

Great question! Let's break down the time complexity of the regex operation here step by step:

• Time complexity of re.findall('\d+', s):
  The pattern \d+ matches one or more consecutive digits. Unlike complex regex patterns that trigger backtracking (like nested quantifiers or multiple alternations), this pattern is straightforward and linear. Python's re module scans the input string s exactly once:

  • It skips non-digit characters until it hits a digit.
  • Then it continues scanning until it encounters a non-digit, grouping that entire sequence of digits as a single match.
  • No backtracking happens here—each character in the string is checked exactly once. For a string of length n, this means the re.findall() operation runs in O(n) time.

• Context of the full code:
  The subsequent map(int, ...) converts each matched digit string to an integer. Each conversion takes O(m) time (where m is the length of the digit string), but summing all m values across all matches equals the total number of digits in s—which is at most n. The sum() operation adds these integers, running in O(k) time (k is the number of matches, which can't exceed n). Both steps are still dominated by the O(n) time of the regex scan.

In short, the regex method (re.findall()) in this code has a linear time complexity, O(n), where n is the length of the input string s.

内容的提问来源于stack exchange，提问作者codemonk1307