Interview Question — Longest regex match with single wildcard

Правка en1, от perlentaucher, 2024-03-16 14:30:48

Hi there, I was given the following interview question and was wondering, if there's a more simple way to solve it:

Question: Given a text and a regular expression that only contains one wildcard character '*' (which matches any string), return the length of the longest matched substring in the text. Return -1 if no answer can be found. 1 <= |Text|, |Regex| <= 10^6.

Example: text = "programming", regex = "r*in". The matches are "rammin", "rogrammin", thus the answer is 9.

My solution: I make a case distinction based on whether the regex is of the form (BEFORE*AFTER, AFTER, BEFORE, *). I then use the Z-Function on the string to get matches of BEFORE and AFTER and then select the first/last matches to calculate the length.

Time/space complexity is obviously O(n) but I think that my solution is a bit overcomplicated.

Теги interview, regex, string match

История

 
 
 
 
Правки
 
 
  Rev. Язык Кто Когда Δ Комментарий
en1 Английский perlentaucher 2024-03-16 14:30:48 910 Initial revision (published)