HolkinPV's blog

By HolkinPV, 10 years ago, translation,
It was assumed a such solution. Firstly, if the lengths of strings were not equal, obviously the answer is -1. In the other case for all positions we search for all letters and try to make changes to the current letter. To make it quick, we will precalc a matrix Z[26][26], in which the сell (i, j) - is the minimum cost of change of i-th the letter of the alphabet to j-th. It can be done for example by Floyd algorithm. If at some position there is no possible letter, the answer is -1. In the other case, we should sum the answer for all positions and write the resulting string.

• +5

 10 years ago, # |   0 I created a 2d Graph and did a simple Floyed to relax all the edges as explained .. then looped on the Strings and every time I found two characters don't match I try to find Min(graph[a][k]+graph[b][k]), where 0<=k<=25 ,and 'a' ,'b' is the character in the first ,second String respectively. However I'm getting a TLE on case 26 :/ .. any clue ? .. here's my code :
•  10 years ago, # ^ |   +1 Use StringBuilder to construct the final result. Usage of += with the String is a slow operation.
•  10 years ago, # ^ |   0 Accepted ! :) .. amazing yet frustrating :S :/ :/ .. Thanks alot :)..
•  10 years ago, # ^ |   0 My friends had TL on case 26 but because of the different string error.He used C-style strings char* and in the loop he wrote strlen(s).Don't do this because this operation costs O(length of the string).C++-style strings are more convenient for this case and s.size() is OK.
•  10 years ago, # ^ |   0 Or just store the strlen(s) in a variable. Char array is faster than the C++ string, so I suggest you to use it when you can.