Edit Distance Backtrack Pseudocode

E[m][n] matrix
str1 = string1
str2 = string2

----------------------------------
  TraceBack()
----------------------------------
   SequenceQueue L1
   SequenceList  L2
 
   sequence SEQ = ''
   L1.add(SEQ)

   while(L1 is not empty):

currentSeq = L1.remove()

i = len(str1)
j = len(str2)


//If currentSeq is other OPTIMUM SEQUENCE, which is bifurcated from earlier one,
        //we need to assign correct relevant values of i and j as follows

for value in currentSeq:
if ( value == "S" ):
i--
j--

if ( value == "U" ):
i--

if ( value == "L" ):
j--


//From here we will do actual traceback for E[i][j] using,
        //E[i-1][j-1]   E[i-1][j]      E[i][j-1]
 
while ( i>=1 && j>=1 ):

slant=left=up=""
min = 0

//we use i - 1 because it is ith value in str1 [0...m-1] and in E, E[1][j] to E[m][j] is str1
//we use j - 1 because it is jth value in str2 [0...n-1] and in E, E[i][1] to E[i][n] is str2

if ( str1[i - 1] == str1[j - 1] ):  //this is Character corresponding to E[i][j] i.e. ith in str1 and jth in str2
left  = (E[i][j - 1]) + 1;
up    = (E[i - 1][j]) + 1;
slant = (E[i - 1][j - 1]);

min = min(left, up, slant);

else:
left = (E_GLOBAL[i][j - 1]) + 1;
up = (E_GLOBAL[i - 1][j]) + 1;
slant = (E_GLOBAL[i - 1][j - 1]) + 1;

min = min(left, up, slant);



if (E[i][j] == slant): //If minimum is slant

currentSeq.add("S");

if (E[i][j] == up):  //If minimum is also up
Sequence seq2 = ""
seq2.add("U");
sequenceList.add(seq2);

if (E[i][j] == left): //If minimum is also left
Seqeunce seq3 = ""
seq3.add("L");
sequenceList.add(seq3);

i--;
j--;

else if (E[i][j] == up): //If minimum is up

currentSeq.add("U");

if (E[i][j] == left): //If minimum is also left

Seqeunce seq3 = ""
seq3.add("L");
sequenceList.add(seq3);

i--;

else if (E[i][j] == left):
seq.add("L");
j--;


reverse(currentSeq);
L2.add(currentSeq);

---------------------------------
OUTPUT: SequenceList  L2
---------------------------------


Time Complexity   O(n^2)
Space Complexity  O(n^2)