# HR Write-up: Abbreviation

A mix of string comparison and dynamic programming.

# Question

# Sketch of the Solution

We start investigating from the last characters of both strings. We create variables `pa`

and `pb`

to keep track of the current indexes of `a`

and `b`

. So, at the initial state, `pa = len(a) - 1`

and `pb = len(b) - 1`

. The original question is rephrased as *given the transformation rules, can we make b[:pb+1] from a[:pa+1]?*

Note that when `a[pa]`

is a lowercase letter and `a[pa].upper() == b[pb]`

, we have two possibilities; 1. capitalizing `a[pa]`

to make a pair with `b[pb]`

and 2. deleting `a[pa]`

to virtually skip that character. We have to chase down both of the cases.

We can say `a`

is an abbreviation of `b`

if `pb < 0 and (pa < 0 or a[:pa+1].islower())`

.

In more complicated cases, we need memoization to reduce the traversal time. Take a look at the following picture.

As I have grouped with a dotted rectangle in the picture, there is a duplicate case in the tree. We should skip those cases to save computational time. We can achieve that by memoization. The idea is that you bring a set of indexes you have already visited in the journey of finding the *YES* pattern and check if the current state has already been examined. If so, you do not need to do the same computation again.