← All solutions

Let L be the length of the starting and target strings, and consider a directed graph G = (V, E) on strings of length L, where there is an edge from a string x to a string y if x can be transformed to y using one of the suffix-replacement rules. The problem asks for the shortest path from S to T in this graph—however, the graph has 52 L vertices and hence finding a shortest path by a standard BFS is not feasible.

What saves us is the fact that the graph in question has a very special structure. Consider a path from S to T. Some of the transformation rules used involve suffixes of length L, and the remaining transformation rules used involve shorter suffixes. The basic idea is to precompute shortest paths in the subgraph of G which only uses transformation rules involving shorter suffixes.

Specifically, let Gl be the analogue of the graph G defined above on strings of length l (note that the edges of this graph correspond to the transformation rules involving suffixes of length at most l), and let Dl ( x, y) be the length of a shortest path from a string x to a string y (both of length l) in Gl . Consider a weighted directed graph Hl consisting of strings of length l, where the edges are as follows:

• There is an edge from x to y of cost 1 if there is a transformation rule transforming x to y
• There is an edge from x to y of cost Dl −1 ( x 0 , y0 ) if the first two charactes of x and y are equal and x 0 , y0 denote the suffixes of x and y obtained by removing the first character.

Then, the shortest path lengths in Hl are exactly the same as those in Gl . In other words, Dl ( x, y) is given by the length of a shortest path from x to y in Hl . So, one (seemingly awkward) way of computing the shortest path from S to T in G (i.e., DL (S, T )) is to iteratively compute the shortest path lengths in Hl for l from 1 to L (since the definition of Hl involve the shortest path lengts in Hl −1 ).

Now, how does this help? The number of vertices of Hl is still 52l ! Recall that the quantity that we are actually interested in is DL (S, T ). Note that to compute this, the only vertices of HL which are relevant, apart from S and T themselves, are those which occur as either lefthand or righthand side of some transformation rule. More generally, unwinding the definitions, one sees that the only vertices in Hl (i.e., the only strings of length l) that one has to consider are those which are suffixes of one of the 2R + 2 input strings. With this good bound on the effective sizes of the graphs, computing all the relevant shortest paths lengths in Hl can be done using e.g. Floyd-Warshall. A somewhat tricky point in this problem is that the length of a path can be exponentially large in the length of a string, so it may be the case that an answer does not fit in a 32-bit integer.