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.


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
  • 1
    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

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.