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.
