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;

1. if only one pointer is at end, impossible to match more, return false

2. if not a digit, check if equal, recurse down

3. 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