# Facebook Interview Question: Given a regular expression wit Search

In Facebook Engineering Interview, you may be asked to do linear search on given String using reggex pattern.

Here is the detailed Question For Search Algorithm:

Facebook Coding Question: Given a regular expression with characters A-Z, ‘ * ‘, ‘ . ‘ (Ex: AB.*D*). Check if that pattern matches to given string and return flag true. Return false otherwise.

Here are the clarifications we need to keep in cosideration.

```Clarifications:

'.' => Any character
'*' => 0 to N occurrence of preceding element(for ".*").
'*' => Any character ( for "A*" )
'*' => N occurrence ( for "A*" ).
```

Sample Data:

Example1: Input String: “ABCDDE”, Input Regex: AB.*D* Output: true

In This Example we are comparing characters in input string and input regex.

• Step1: AB are present in Both given String and also in given Regex.
• Step2: “.” means Any character so basically we don’t need to compare at all.
• Step3: “*” means we need to check character after that character and it should be the same character as it is next to “.”. We can easily check using str[currenti] === str[currenti+1] comparison.
• Step4: “D” is present in Both given String and also in given Regex.
• Step5: Lastly for “*” as it doesn’t have “.” before it, it could be any character and could be N occurrences.

Now we know the execution and comparison steps we need to solve this problem, we can add it to working program using Javascript.

``````const testRegex = (str, ptrn) => {
let flag = true;
for (let i = 0; i < str.length; i++) {
if (str[i] !== ptrn[i]) {
if (ptrn[i] === '.') {

} else if (ptrn[i] === '*' && flag === true) {

} else if (ptrn[i] === '*' && ptrn[i-1] === '.') {
flag = true;
const char = ptrn[i+1];
if (char === str[i]) {

}
else {
return false;
}
} else {
return false;
}
}
}
return true;
}
console.log(testRegex('ABCDDE', 'AB.*D*'));``````

Try on Coding Playground to test it out: