Mark Ransew
BAN USER- 1of 1 vote
AnswersWe have two strings: a normal alphanumeric string and a pattern string. the pattern string can be composed by alphanumeric chars plus the char "?" and "*"
We want to check if the first string match the pattern, where the ? means that every char (alphanumeric) is permitted in that position, while * allows to have a sequence of alphanumeric chars.
as test we want to check that the function returns true to the following calls.
isMatching("abab","abab")
isMatching("abab","a**b")
isMatching("ababab","ab*b")
isMatching("","*")
isMatching("aaaaaab","*?*b")
i found this question hard, since the language we want to parse is not L1 (there's an ambiguity in the parsing tree) it means that a backtrack modality must be implemented.
Took me a while to find a reasonable solution (that, to be honest i was not happy with)
- Mark Ransew in United Statesfunction isLegal(string:String,pattern:String):Boolean{ if(pattern.length == 0 && string.length == 0) return true; if(pattern.length == 0 && string.length > 0) return false; // NOT PROUD OF THE FOLLOWING CONDITION if(pattern.length == 1 && string.length == 0){ if(pattern.charAt(0) == "*") return true; } if(isLetter(pattern.charAt(0))){ if(string.charAt(0) == pattern.charAt(0)){ // CHAR BY CHAR CONTROL return isLegal(string.substr(1),pattern.substr(1)); } return false; } else if(pattern.charAt(0) == "?"){ if(isLetter(string.charAt(0))){ // RECURSIVE CALL return isLegal(string.substr(1),pattern.substr(1)); } return false; } else if(pattern.charAt(0) == "*"){ var possibleSolution:Boolean = false; for(var i:int = 1; i< string.length && !possibleSolution;i++){ possibleSolution = isLegal(string.substr(i),pattern.substr(1)); } return possibleSolution; } else { // ILLEGAL PATTERN return false; } } function isLetter(s:String):Boolean{ return s.charCodeAt(0) > 96 && s.charCodeAt(0)<122; }
| Report Duplicate | Flag | PURGE
Google Software Engineer / Developer Algorithm
I said the same to the interviewer, and even if he agreed on the problem identification, he also suggest to go for an easier solution without involving automaton.
- Mark Ransew July 31, 2013i asked if i could use any Regular Expression but he said no
- Mark Ransew July 31, 2013
i'm really impressed of the memoization addon.
- Mark Ransew July 31, 2013