Nielsen Interview Questions

You are asked to implement a simple regex parser which supports two operations: '.' and '*'. The '.' operation matches any single character, while the '*' operation matches zero or more of the preceding element. The matching should cover the entire input string (not partial).

Write a function isMatch(s,p) which takes in two parameters, the string and the regex pattern. It should return a Boolean output indicating a ‘match success’ or a ‘match failure’.

Example 1:

Input:

s = 'aa'
p = 'a'

Output:

isMatch(s, p) -> False

Explanation: ‘a’ does not match the entire string ‘aa’.

Example 2:

Input:

s = 'aa'
p = 'a*'

Output:

isMatch(s, p) -> True

Explanation: ‘*’ means zero or more of the preceding element, ‘a’. Therefore, by repeating ‘a’ once, it becomes ‘aa’.

Note: There is no need to consider the delimiting of characters ‘.’ and ‘*’