String Abbreviation Matching
Word “book” can be abbreviated to 4, b3, b2k, etc. Given a string and an abbreviation, return if the string matches the abbreviation.
Assumptions:
The original string only contains alphabetic characters.
Both input and pattern are not null.
Pattern would not contain invalid information like "a0a","0".
Examples:
pattern “s11d” matches input “sophisticated” since “11” matches eleven chars “ophisticate”.
Solution: Straight down tail recursion
Base Case: if both pointers travelled to end, return true
Recursive rule;
if only one pointer is at end, impossible to match more, return false
if not a digit, check if equal, recurse down
if is a digit, travel that many digits, recurse down
public boolean patternMatch(String s, String t, int si,int ti){
if ( si == s.length() && ti == t.length()) return true;
if (si >= s.length() || ti >= t.length()) return false;
if (t.charAt(ti) < '0' || t.charAt(ti) > '9'){
if (s.charAt(si) == t.charAt(ti)){
return patternMatch(s, t, si + 1, ti + 1);
}
return false;
}
int count = 0;
while (ti < t.length() && t.charAt(ti) >= '0' && t.charAt(ti) <= '9'){
count = count * 10 + (t.charAt(ti) - '0');
ti++;
}
return patternMatch(s, t, si + count, ti);
}
Time Comp: O(N) one traversal, no branching
Space Comp: O(N) tail recursion, returns when at end of string
Last updated
Was this helpful?