(Uber Phone interview) string pattern matching

• The matching should cover the entire input string (not partial).
The function prototype should be:

bool isMatch(String str, String patter)
Some examples:
isMatch("aa","a") → false
isMatch("aa","aa") → true
isMatch("aaa","aa") → false
isMatch("aa","a{1,3}") → true
isMatch("aaa","a{1,3}") → false
isMatch("ab","a{1,3}b{1,3}") → true
isMatch("abc","a{1,3}b{1,3}c") → true
isMatch("abbc","a{1,3}b{1,2}c") → false
isMatch("acbac","a{1,3}b{1,3}c") → false
isMatch("abcc","a{1,3}b{1,3}cc{1,3}") → true

• a{1,3} means aaa, the right } is exclusive

• @daniel.w.1 Do you mean that a{1,3} means that count of a's could be 1, 2 or 3, e. g a, aa, aaa is valid in this case? Thanks

• @elmirap only 'a' and 'aa' are valid, because the right parenthesis is exclusive. a{1,3} essentially means 'a' can be repeated from index 1 to index 2, cannot be repeated at index 3 because right parenthesis is exclusive.

• @daniel.w.1 What happens if pattern is a{4,5} b{1,2} ? Could you specify valid string for this pattern?
Is it aaaab valid? Also could exist a pattern a{1,3}a?

• @elmirap I have to ask the original problem poster, get back to u soon

• @daniel.w.1 thanks I will be waiting for your clarification

• @elmirap I think a{4,5} means aaaa, and a{1,2} means a

• @moooc Is it possible to have a{1,3}a ? What do you think?

• @elmirap : if a{4,5} means aaaa then what is the difference between a{1,5} and a{4,5
}?

• Simple backtracking based pattern recognition solution

``````class Solution:
def UBER_patternMatching(self, str, pat):
"""
:type str: string
:type pat: string
:rtype: bool
"""
if not pat:
return not str
minReps = 1
maxReps = 1
closeBraces = 0
char = pat[0]
if len(pat) > 1:
if pat[1] == '{':
closeBraces = pat.find('}')
rangeSubstr = pat[2:closeBraces]
leftStr, rightStr = rangeSubstr.split(',')
maxReps = int(rightStr)
minReps = int(leftStr)
# print(minReps, maxReps)
cntr = 0
while cntr < minReps:
if str[cntr] != char:
return False
cntr += 1
newStr = str[minReps:]
newPat = pat[closeBraces+1:]
if maxReps > minReps:
diff = maxReps - minReps
for i in range(0, diff):
newPatDiffed = char*i + newPat
# print(newPatDiffed, newStr)
success = self.UBER_patternMatching(newStr, newPatDiffed)
if success:
return True
return False
else:
return self.UBER_patternMatching(newStr, newPat)
``````

• ``````class Solution(object):
def isMatched(self, s, p):
def dfs(s, si, p, pi):
while si < len(s) and pi < len(p) and s[si] == p[pi]:
si += 1
pi += 1
if si == len(s) and pi == len(p):
return True
if pi < len(p) and p[pi] == "{":
c = p[pi - 1]
start = pi
while pi < len(p) and p[pi] != "}":
pi += 1
left, right = map(int, p[start+1:pi].split(","))
for k in range(left, right):
if s[si:si + k - 1] == c * (k - 1):
if dfs(s, si + k - 1, p, pi + 1):
return True
return False
return dfs(s, 0, p, 0)
``````

• I've tried and came up with this following. Just tried a couple of test cases though. No edge case test or whatsoever. Hope someone can give me a feedback.

'''
public static boolean isMatcheeing(String input, String pattern){

``````    char prevPattern = Character.MIN_VALUE;
for (int i = 0; i < input.length(); i++){
if (input.charAt(i) != pattern.charAt(i)){
if (pattern.charAt(i) == '{'){
String inBrace = "";
for (int j = i+1; j < i+5; j ++){ // this is constant time
if (pattern.charAt(j) == '}'){
ArrayList<String> options = getPatternOptions(prevPattern, inBrace);
boolean valid = false;
for (String subpattern : options){
String comparee = input.substring(0, i) + subpattern;
if (input.startsWith(comparee)){
valid |= isMatcheeing(input.substring(comparee.length()), pattern.substring(j+1));
}
}
return valid;
} else {
inBrace += pattern.charAt(j);
}
}
} else {
return false;
}
}
prevPattern = pattern.charAt(i);
}
return true;
}

public static ArrayList<String> getPatternOptions(char prev, String subStr){

int lowerB = Integer.valueOf(subStr.split(",")[0]);
int upperB = Integer.valueOf(subStr.split(",")[1]);

ArrayList<String> options = new ArrayList<>();
String subPattern = "";
for (int i = lowerB; i < upperB; i++){ // we already used one char in the previous comparision
subPattern += prev;