Amazon Interview Question Member Technical Staffs
Country: India
Interview Type: In-Person
bool PatMatch(string text, string pat) {
/* Traverse again */
char prev = '1';
int charcnt_text = 0, charcnt_pat = 0;
int patlen = pat.length();
int textlen = text.length();
int j = 0; // text itr
for(int i=0;i<patlen;i++) {
if(j == textlen)
return false;
if(pat[i] == '?') {
prev = text[j++];
} else if(pat[i] == '*') {
while(text[j] == prev) {
j++;
charcnt_text++;
}
/* find charcnt_pat */
int k = i+1;
while(pat[k] == prev) {
k++;
charcnt_pat++;
}
if(charcnt_text - charcnt_pat < 0) {
return false; /* atleast one needed */
} // dont bother abt rest of same char
i = k-1; // will be inc by loop
} else {
if(pat[i] != text[j])
return false;
prev = text[j++];
}
}
return true;
}
Javascript:
var text = "abcd"
var singularMatch = function(input, char) {
return char=='?' || input==char;
}
var regex = function(input, pattern) {
var originalPattern = pattern;
for(var i=0; i<input.length && pattern.length > 0; i++) {
console.debug(pattern)
if(pattern.length>1 && pattern[1]=='*') {
if(singularMatch(input[i], pattern[0])) {
if(input.length>i+1
&& pattern.length>2
&& input[i+1] == pattern[2]) {
pattern = pattern.substring(2)
}
else {
continue;
}
}
else {
pattern = pattern.substring(2)
}
}
else if(singularMatch(input[i], pattern[0])) {
pattern = pattern.substring(1)
}
else {
return regex(input.substring(1), originalPattern);
}
}
return pattern.length==0;
}
var sysout = function() {
document.body.innerHTML += '<br/>'+Array.prototype.slice.call(arguments).join()
}
sysout("abcd", regex("abcd", "ab?d"))
sysout("abccdddef", regex("abccdddef", "ab?*f"))
sysout("abccd", regex("abccd", "ab?*ccd"))
We may use DP, following is code in Java:
public class RegularMatcher {
private static boolean isMatching(char a, char b){
return a == b || b == '?' || a == '?';
}
private static boolean isMatching(String text, String patten){
int tlen = text.length(), plen = patten.length();
/* step 1: allocate memory to store states */
boolean[][] dp = new boolean[tlen + 1][plen + 1];//all false initially
/* step 2: initialize */
dp[tlen][plen] = true;
/* step 3: DP */
for(int i = tlen - 1; i >= 0; --i){
char t = text.charAt(i);
for(int j = plen - 1; j >= 0; --j){
char p = patten.charAt(j);
if(p != '*')
dp[i][j] = isMatching(t, p) && dp[i+1][j+1];
else
dp[i][j] = isMatching(t, patten.charAt(j-1)) &&
(dp[i+1][j+1] || dp[i+1][j]);
}
}
/* step 4: return result */
return dp[0][0];
}
public static void main(String[] args){
System.out.println(isMatching("abcd", "ab?d"));
System.out.println(isMatching("abccdddef", "ab?*f"));
System.out.println(isMatching("abccd" , "ab?*ccd"));
}
}
This is recursive function where ti is start index of text and pi is start index of pattern
boolean match(char[] text, int ti, char[] pattern, int pi){
int tlen = text.length, plen = pattern.length;
if(text[ti] == pattern[pi] || pattern[pi] == '?'){
if(tlen-1 == ti && plen-1 == pi){
return true;
}else if(tlen-1 > ti && plen-1 > pi){
return match(text, ti+1, pattern, pi+1);
}
}else if(pattern[pi] == '*'){
if(tlen-1 >= ti && plen-1 == pi){
return true;
}else if(tlen-1 > ti && plen-1 > pi){
return match(text, ti+1, pattern, pi+1)
|| match(text, ti+1, pattern, pi);
}
}
return false;
}
In Java
import java.util.regex.Matcher;
import java.util.regex.Pattern;
import org.junit.Assert;
import org.junit.Test;
public class PatternMatchingChallenge {
@Test
public void test() {
Assert.assertTrue(isMatch("ab?d", "abcd"));
Assert.assertTrue(isMatch("abc?*f", "abccdddef"));
Assert.assertTrue(isMatch("abc*d*ef", "abccdddef"));
Assert.assertFalse(isMatch("abccd", "ab?*ccd"));
}
public boolean isMatch(String expression, String input) {
String regExpression = expression.replaceAll("\\?\\*", "\\\\w{2,}");
regExpression = regExpression.replaceAll("\\?", "\\\\w");
regExpression = regExpression.replaceAll("\\*", "{2,}");
Pattern p = Pattern.compile(regExpression);
Matcher m = p.matcher(input);
return m.matches();
}
}
Hi,
I don't know how the second test case is working.
But i suppose if text = "abccdddef" and pattern = "c?*e", then it should return true.
Please find my simple sols by brute force method where
Logic is pretty straight forward
If a "?" is found then just increment the counter, without checking for any match.
If "*" is encountered then take the character before "*" and start moving forward in text until unmatched chracter is foudn
if "?*" is encountered then take the character to be matched from text and not pattern. And use the same above logic of *
public static boolean patternMatch(String t, String p){
char text[] = t.toCharArray();
char patt[] = p.toCharArray();
int n = text.length;
int m = patt.length;
for(int i=0; i < n-m; i++){
int count = 0;
int x = i;
for(int j=0; j < m; j++){
if(patt[j] == '?'){
x++;
count++;
}
else if(patt[j] == '*'){
char ast = patt[j-1];
if(ast == '?'){
ast = text[x-1];
}
while(text[x] == ast){
x++;
}
count++;
}
else if(text[x] == patt[j]){
x++;
count++;
}
else{
continue;
}
if(count == m){
return true;
}
}
}
return false;
}
}
Answer in Python:
def matchSingle(c, p):
return c==p or p=='?'
def match(text, pattern, lastChar=None):
# print "match:", text, pattern
textCount=0
tCount=0
pCount=0
while tCount<len(text) and pCount<len(pattern):
# print tCount, pCount
if matchSingle(text[tCount], pattern[pCount]):
lastChar=pattern[pCount]
tCount=tCount+1
pCount=pCount+1
continue
if pattern[pCount]=='*':
if lastChar is None:
raise Exception
if matchSingle(text[tCount], lastChar):
if match(text[(tCount+1):], pattern[pCount:], lastChar):
return True
tCount=tCount+1
pCount=pCount+1
continue
if pCount==0:
tCount=tCount+1
else:
textCount=textCount+1
pCount=0
if pCount==len(pattern):
return True
return False
match("abcdef","abc")
match("aabbbcdef","a*b*c")
match("abcd", "ab?d")
match("abccdddef", "ab?*f")
match("abccd", "ab?*ccd")
def pattern(s1, s2):
m = len(s1)
n = len(s2)
i = j = 0
while i < m and j < n:
if s1[i] == s2[j] or s2[j] == '?':
print s1[i], s2[j]
i += 1
elif s2[j] == '*':
print s1[i], s2[j]
k = i
i += 1
while i < m and s1[k] == s1[i]:
print s1[i], s2[j]
i += 1
else:
print s1[i], s2[j]
return False
j += 1
if i != m or j != n:
return False
return True
def pattern(s1, s2):
m = len(s1)
n = len(s2)
i = j = 0
while i < m and j < n:
if s1[i] == s2[j] or s2[j] == '?':
print s1[i], s2[j]
i += 1
elif s2[j] == '*':
print s1[i], s2[j]
k = i
i += 1
while i < m and s1[k] == s1[i]:
print s1[i], s2[j]
i += 1
else:
print s1[i], s2[j]
return False
j += 1
if i != m or j != n:
return False
return True
int main(){
char *text[] = {"abcd",
"abccdddef",
"abccd",
NULL};
char *pattern = {"ab?d",
"ab?*f",
"ab?*ccd",
NULL};
for(int i = 0; (t = text[i]) && (p = pattern[i]); ++i){
match = true;
while(*p && *t){
if(*p == '*'){
if(!match || *mp != *t) {++p; match = true;}
else ++t; //consume {<a-z>* pattern from text}
}
else if(*p == '?')
++p; ++t;
}
else{
if(!match) break;
if(*p != *t) {match = false;}
else {match = true; mp = t; ++t;}
++p;
}
}
if(!match || *p) printf("false\n");
else printf("true\n");
}
}
public static bool PatternMatches(string s, string pattern)
{
int i = 0;
int j = 0;
char charToMatch = '\0';
while (true)
{
if (i == j && i == s.Length)
return true;
if (i < s.Length && j == pattern.Length)
return false;
if (pattern[j] != '*' && pattern[j] != '?')
{
if (s[i] == pattern[j])
{
i++;
j++;
continue;
}
else
return false;
}
if (pattern[j] == '?')
{
charToMatch = s[i];
i++;
j++;
continue;
}
Debug.Assert(charToMatch != '\0');
if (pattern[j] == '*')
{
while (s[i] == charToMatch && i < s.Length)
i++;
j++;
charToMatch = '\0';
}
}
}
Backtracking approach: ?* matches the rest of the string, but then when you see the pattern has more after ?* you tbacktrack, i.e take the string that you greedily matched with ?* and evaluate the rest of the pattern.
The way you do that, for eg. ?* of pattern fdde?*dde matched hlmddef of fddehlmddef . and you still have dde* in the pattern. You traverse the matched string hlmddef from end to beginning, and then calling this main Match function recursively from Substring(currentIndex, StringLength) for remaining pattern dde.
Note there needs to be atleast one additional element in the matched string not matched by the remaining pattern, to account for the fact that previous ?* HAS to match atleast one character.
If the you want to avoid the backtracking then, you match ?* with as little characters as possible, i.e. you iterate over the remaining string and try to match the rest of the pattern (Recursively). This seems a bit more elegant/easy to follow, with no savings over the other.
bool match(char *a,char *b)
{
if(*a=='\0'&&*b=='\0')
return true;
if(*a=='*'&&*(a+1)!='\0'&&*b=='\0')
return false;
if(*a=='?'||*a==*b)
return match(a+1,b+1);
if(*a=='*')
return match(a+1,b)||match(a,b+1);
return false;
}
Ex text = "abccdddef" pattern = "ab?*f" True
- pa July 08, 2014Is this correct?
ab - ab
c - ?
c - *
d - f
false