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.

Examples:

• pattern “s11d” matches input “sophisticated” since “11” matches eleven chars “ophisticate”.

Solution 1: Iterative. 当pattern指针指向字母时，看是否与input指针指的一样；当pattern指针指向数字时，求得value，再把input指针i += value.

  public boolean match(String input, String pattern) {
    int i = 0, j = 0;
    while (i < input.length() && j < pattern.length()) {
      char c = pattern.charAt(j);
      if (c >= 'a' && c <= 'z' || c >= 'A' && c <= 'Z') {
        if (c == input.charAt(i)) {
          i++;
          j++;
          continue;
        } else {
          return false;
        }
      }
      int val = 0;
      while (j < pattern.length() && pattern.charAt(j) >= '0' && pattern.charAt(j) <= '9') {
        val = val * 10 + pattern.charAt(j) - '0';
        j++;
      }
      i += val;
    }
    return i == input.length() && j == pattern.length();
  }

Solution 2: recursion (tail recursion, 所以容易用iterative)