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