String Abbreviation Matching
Iterative optimization from recursive version
public boolean match(String input, String pattern) {
//base case: si and ti at end, true
//Recursive Rule:
//if si or ti out of bounds, false
//if not digit, check equal, recurse si + 1, ti + 1
//if digit, count digit, increase ti and si
//Recursive impl on gitbook
//iterative
int si = 0;
int ti = 0;
while (si < input.length() && ti < pattern.length()){
if (pattern.charAt(ti) < '0' || pattern.charAt(ti) > '9'){
if (pattern.charAt(ti) != input.charAt(si)){
return false;
}
si++;
ti++;
} else {
int count = 0;
while(ti < pattern.length() && pattern.charAt(ti) >= '0' && pattern.charAt(ti) <= '9'){
count = count * 10 + (pattern.charAt(ti) - '0');
ti++;
}
si += count;
}
}
return si == input.length() && ti == pattern.length();
}
Time Comp: O(N) one traversal
Space Comp: O(1) no addition data structure or calls made on stack
Last updated
Was this helpful?