randm question is on the spot. Making an automata from a regular expression really takes a lot of work and it's not realistic in my opinion to ask that in an interview. What I think is most probable is that they asked for a regular expression that does not contain parentheses, i.e it consists only of characters and wildcards, such as a*b*cde*f. Such regular expression can be easily matched by a greedy linear time algorithm. in this example, check that the first character of the string is an a, then look for the first occurrence of 'b' after 'a', then look for the first occurrence of "cde" after b, then check that the last character is an 'f'. A similar method can work for all regular expressions without parentheses. But if you have parentheses, expressions like (a(a*b)*) where * denotes kleene closure, you will need to convert the expression first to a non-deterministic finite automaton, then to a deterministic finite automaton, which is a very time consuming to do, and which take exponential time in the length of the regular expression (although it takes linear time in the length of the string to match). If the regular expression is long, it is better to use Dynamic Programming to parse the expression (for example we can use a variant of the Cocke-Kasami-Younger algorithm).

hi anonymous ^ even I thought that the simple greedy algo proposed by you is correct, but it could be wrong for example if pattern is a*b*cd*ef and the string is abcdetklabcdef then the greedy approach would fail immediately [assuming you do not backtrack, O(n) algo as in kmp) well if you do an O(n^2) approach only then that approach gives correct answer. I wrote code & verified, can share incase.

Hello light, I don't see why the simple greedy algorithm would fail on the pattern you indicated. pattern a*b*cd*ef string abcdetlabcdef first match a then b then cd so a*b*cd matches abcd and then check that the last characters are ef as indicated in the pattern. Hence a*b*cd*ef, provided as you say that we use a O(n) algorithm for string matching such as Knuth Morris Pratt (KMP)

I really doubt it. This is a question for a permanent job so I believe that there was a lot of time to work this problem out. My solution would be to make automata from regular expression then hit the string in it to check is it lexically correct.