Last active
February 17, 2019 06:06
-
-
Save robbywashere-zz/a808107f3d7e5212e463fb4d1038f834 to your computer and use it in GitHub Desktop.
simple wild card regex implementation in javascript (interview question)
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
| /* | |
| Implement regular expression matching with the following special characters: | |
| * . (period) which matches any single character | |
| * * (asterisk) which matches zero or more of the preceding element | |
| That is, implement a function that takes in a string and a valid regular | |
| expression and returns whether or not the string matches the regular expression. | |
| For example, given the regular expression "ra." and the string "ray", your | |
| function should return true. The same regular expression on the string "raymond" | |
| should return false. | |
| Given the regular expression ".*at" and the string "chat", your function should | |
| return true. The same regular expression on the string "chats" should return | |
| false. | |
| */ | |
| const assert = require('assert'); | |
| function rx(str, ptn){ | |
| if (str === "" && ptn === "") return true; | |
| if (str === ""){ | |
| if (ptn.substr(1,1) === "*") return rx("",ptn.slice(2)); | |
| return false; | |
| } | |
| if (ptn.substr(1,1) === '*') return rx(str.slice(1),ptn.slice(2)) || rx(str,ptn.slice(2)) | |
| || rx(str.slice(1),ptn); | |
| if (ptn.substr(0,1) === '.') return rx(str.slice(1),ptn.slice(1)); | |
| if (ptn.substr(0,1) === str.substr(0,1)) return rx(str.slice(1),ptn.slice(1)); | |
| } | |
| assert.equal(rx('chat','ch.t'), true) | |
| assert.equal(rx('chat','ch.*at'),true) | |
| assert.equal(rx('chat','c.*at'),true) | |
| assert.equal(rx('chXXXXat','chX*at'), true) | |
| assert.equal(rx('chXXXXats','chX*at'), false) | |
| assert.equal(rx('chat','ch.*at'),true) | |
| assert.equal(rx('chat','.*at'),true) | |
| assert.equal(rx('chatat','.*at'),true) | |
| assert.equal(rx('ccchatathatat','.*at'),true) | |
| assert.equal(rx('chatsssss','.*at.*'), true) | |
| assert.equal(rx('chat','.*at.*'), true) | |
| assert.equal(rx('chat','.*at.*k*l*w*x*'), true) | |
| assert.equal(rx('chatsssss','.*at.*x'), false) | |
| assert.equal(rx('chats','.*at'), false) | |
| assert.equal(rx('chats','.*at'), false) |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment