About Me

▼

Monday, July 11, 2011

You have to write a function checkRegex() which takes two strings as input, one string represents a regex expression and other is an input string to match with the regex expression passed as the other parameter. Return true if it matches, else false.

I found this question on one of the forum

Regex may contain characters ‘a-z’, ‘.’ and ‘*’ where ‘.’ matches any character and ‘*’ means 0 or more occurrences of the previous character preceding it.

Examples:
1) a*b matches b,ab,aab
2) a.b matches aab, abb, acb,…, azb
3) .* matches all the valid strings formed by using the lowercase letters


Status: Solved

Algorithm:Recursion



Time Complexity O(2^n)
Space Complexity O(1)
at

4 comments:

  1. sankalp srivastavaJuly 13, 2011 at 8:10 AM

    How are you doing it in O(n) without the Deterministic finite automata approach ?

    Is there any other approach to do it in O(n) ??

    The naive approach is O(2^n) in the worst case

    ReplyDelete
  2. UnknownJuly 14, 2011 at 3:42 AM

    @sankalp do mean using recursion

    post your solution i will check it out & then post my solution as well



    Shashank

    ReplyDelete
  3. AnonymousNovember 9, 2011 at 11:04 PM

    Could you please post the solution in O(n).....

    ReplyDelete
  4. UnknownDecember 13, 2011 at 11:09 PM

    @anon . i don' think it can done in O(N) ?

    ReplyDelete

Hi thanks , we will get back to you shortly !!!