Directed Graph, Floyd Algorithm
There are M mappings from lower case English alphabet to lower case English alphabet. Using these mappings, can one transform a string S to another string T?
Let Can[i][j] denote whether the lower case English character i could be transformed to j in some combinations of given mappings. Initially, only Can[i][i] and the given mappings are set to true.
Then, the Floyd algorithm used to compute the transiting property can be adopted here, as the following:
For k = 1 to 26: For i = 1 to 26: For j = 1 t 26: Can[i][j] |= Can[i][k] && Can[k][j]
After that, we have known all possible transformations between lower case characters. To answer the question, we just need to check the reachability between corresponding characters of the two strings S and T.
AUTHOR’S AND TESTER’S SOLUTIONS:
Solutions will be available soon.
Author’s solution can be found here.
Tester’s solution can be found here.