LC: Generalized Abbreviation - spiralgo/algorithms GitHub Wiki

Generalized Abbreviation

The Essence:

At each character, two decisions can be made: abbreviate or keep the character.

Abbreviating would mean incrementing the running abbreviation length. Keeping the character would mean that the running abbreviation should be terminated by placing its length, and placing the current character afterwards.

After reaching the end, the algorithm can erase the effects of each decision at each step to support the other decision with pre-computed solution at that point.

Details:

The procedure described here is an example of a backtracking algorithm. After making some decisions, one can undo the previous decision at each level to make the other decision. At a programming level, this corresponds to undoing the side effects of the previous decision recursively all the way up to the current level, with a base case eventually storing the total results.