> For the complete documentation index, see [llms.txt](https://llssff.gitbook.io/coding-problems/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://llssff.gitbook.io/coding-problems/recusion/string-abbreviation-matching.md).

# 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