- #1
Jamin2112
- 986
- 12
I'm trying to write a function that takes as parameters two strings, textStart and textTarget, and prints out the steps necessary to transform transform the first into the second, with the allowed steps being:
(1) Add a character somewhere in textStart
(2) Remove a character somewhere textStart
I've reached the point in the algorithm where I've made maps for the characters that need removed and added. For instance, if textStart="dude" and textTarget="deck", then my procedure gives needAdded['c']=1, needAdded['k']=1, needRemoved['u']=1, and needRemoved['d']=1.
Now I need to use this information to figure out the proper removal and insertion steps. Let's deal with the removal steps first.
In the example above, 1 'd' needs removed -- the 2nd one of 2 'd's. But how can I design an algorithm to figure out which of the 2 'd's to remove?
For now, I'm just going to go ahead and write an algorithm that removes the first occurrences of letters that need removed, and adds at the beginning the letters that need added, before finally sorting everything.
(I understand the way of doing this with a tree and branch-and-bound algorithm, but I'm not using it. Maybe some other time.)
(1) Add a character somewhere in textStart
(2) Remove a character somewhere textStart
I've reached the point in the algorithm where I've made maps for the characters that need removed and added. For instance, if textStart="dude" and textTarget="deck", then my procedure gives needAdded['c']=1, needAdded['k']=1, needRemoved['u']=1, and needRemoved['d']=1.
Now I need to use this information to figure out the proper removal and insertion steps. Let's deal with the removal steps first.
In the example above, 1 'd' needs removed -- the 2nd one of 2 'd's. But how can I design an algorithm to figure out which of the 2 'd's to remove?
For now, I'm just going to go ahead and write an algorithm that removes the first occurrences of letters that need removed, and adds at the beginning the letters that need added, before finally sorting everything.
(I understand the way of doing this with a tree and branch-and-bound algorithm, but I'm not using it. Maybe some other time.)