Transform one list of objects into another list

Question

This is a theory question so I'm going to use pseudo code.

I have a list of objects that I need to transform into another list.

I implemented the Levenshtein algorithm, and that works just fine, but I need to preserve the objects, and not create new ones. I can brute force it but Id rather find a non O(n*m) way to do this.

[obj1,obj2,obj3] -> [obj1,obj4,obj5,obj2,obj6,obj3]

obj1,obj2,obj3 have to be the same object where the rest are newly created objects.

Anybody know a good algorithm for this?

Answer 1

You could use pattern flyweight, to do that you'll need to maintain created objects in the cache. Strings in java is a good example of this pattern.