# Similar problem to word break

I have a list of strings say L and an array of words say A. I want to find a string from the list L that is a best match to a string created from the permutations of the words in the array.

The array of words has about 200 elements and each string in the List L is of the same length say at max of 150 characters.

Something similar to the word break problem on geeksforgeeks but I am looking for a best match rather than an exact match.

http://www.geeksforgeeks.org/dynamic-programming-set-32-word-break-problem/

My approach till now:

Creating all the word permutations from the array and running the Levenshtein distance to get a good match doesn't seem like a time efficient approach. Considering that generating a list of 200! strings is impractical.

My question is if there is a more efficient or better performing algorithm to solve this problem than my approach above?

• I am not sure what the question is, exactly. What do you mean by "a string created from the combination of the words in the array"? Can you edit this to provide a more specific problem description? – user22815 Oct 20 '14 at 16:52
• Considering there are N permutations that can be created from the words in the array. I want a string from the list L which gives me the best match to one of the N permutations. I get the best match by using levenshtein distance algorithm and run it for each element of list L to all N elements, which I think would be a very slow method. I am looking for something more efficient. I hope this makes my question clearer. – Viraj Oct 20 '14 at 20:13
• like I said, if you could update the question to include that and a more specific problem statement it would help quite a bit. – user22815 Oct 21 '14 at 3:52
• Permutation problems tend to require a LOT of comparisons. Unless you come up with a slick algorithm for your particular problem then the next obvious approach is to try and filter the data to smaller subsets. Thus, you could probably do a first pass filter where you can eliminate the strings in the list that are obviously not going to be a good match. Maybe count the number of matching characters and drop those below some dynamically determined threshold? If that still leaves too many then apply a 2nd filter to whittle things down. Try and hash A to make lookups/comparisons quicker. – Dunk Oct 21 '14 at 14:27