CareerCup

Pseudo Code:

string word1 = <<input>>
string word2 = <<input>>
int lengthWord1 = NumberOfChar(Word1)
int lengthWord2 = NumberOfChar(Word2)
int loop = (lengthWord1<lengthWord2)?lengthWord1:lengthWord2
//First replace the common number of characters.
for(int i=0;i<loop;i++)
{
  replaceCharacter(word1[i],word2[i])
}

//If word2 is still longer , insert those extra characters.
for(int i=lengthWord1;i<lengthWord2;i++)
{
  insertCharacter(word1[i],word2[i])
}

//If word2 is smaller than word1 , delete those extra characters.
for(int i=lengthWord2;i<lengthWord1;i++)
{
  deleteCharacter(word1[i]);
}

This is a classing DP problem:
Google: Edit distance algorithm

allisons.org/ll/AlgDS/Dynamic/Edit/

Algorithm:

1) First trace the string to find out whether given word2 is present in word in as in the same order.

Ex: word1 : MIXABCMIX
Word2 : ABC

word1: AMIXBMIXC
Word2: ABC

If after tracing, if the answer is yes, then we can use delete operation. It will take max of 6 operations..

2) If after tracing, if the answer is no, then we can check for the length of the word2. If the length is greater than word1, then we can use replace till the end of word1 and then insert till the end of word2.

3) If the length is less than word1, then we can use replace till end of word 2 and then delete till the end of word1.

Algo:

int countSteps(String w1, String w2, int steps){
if (w1 or w2 have length 0)
   then return length of w1(if w2 is of zero length) or vice-versa
   // this is basically the number of insert/delete character steps to make 

else
   if(0th character of both strings are equal)
   then return countSteps(w1[1..n], w2[1..m], steps);
   // current characters match in both strings, so go on to the rest of the string
   else
     find minimum of the following three:
     //replace character
     int steps1 = 1+countSteps(w1.substring(1), w2.substring(1), steps);
     //delete character
     int steps2 = 1+countSteps(w1.substring(1), w2, steps);
     //append character
     int steps3 = 1+countSteps(w1, w2.substring(1), steps);
     return steps+ minStep;
}

Solve the longest subsequence problem... then take the sum of the max of respective chunks of chars between each pair of matching chars..

what is the use of dictionary here?