Thursday, October 11, 2012

Concatenate N strings

Concatenate N strings with good optimization

You have n strings with their lengths. You are given an add(string s1,string s2) which would concatenate the string s2 with s1 and return s3. Optimize the cost of concatenation of all these strings into one big string.
Eg: 1,3,2 are the lengths of given strings.
1+3=4
4+2=6
total cost=10
Optimize this total cost?

Strategy:

Make a min heap out of the elements given.
Pop the smallest and the second smallest, add them and again insert that back to the heap.
Finally you will get the minimum cost 

OR
you can sort the array on the basis of length...and then just concatenate on the length of the string.

No comments:

Post a Comment