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:
Leave a Reply