Reorder strings using similarity score algorithm

The name of the pictureThe name of the pictureThe name of the pictureClash Royale CLAN TAG#URR8PPP



Reorder strings using similarity score algorithm



Re-orders a set of strings buzz, fuzz, jazz, fizz.. so that sum of similarity scores between each pair of adjacent strings is the lowest.


buzz, fuzz, jazz, fizz..


buzz-> fuzz (1)
fuzz-> jazz (2)
jazz-> fizz (2)



sum of the scores is 5. If reordered based on lowest(4) final output is


buzz, fuzz, fizz, jazz..

buzz-> fuzz (1)
fuzz-> fizz (1)
fizz-> jazz (2)



My approach is to find Edit distance for every pair of strings and construct a weighted graph where edge represents the edit distance value. Use DFS to find the lowest path.
Is this the efficient solution? can it be done any better?





The way you model the problem gives you basically the en.wikipedia.org/wiki/Travelling_salesman_problem. So this will have exponential runtime (ergo: this solution is not efficient). However, I cannot think of a more efficient way to solve this.
– SaiBot
Aug 10 at 14:37






I believe that you are looking for the shortest Hamiltonian path in a complete graph. Visit each word or vertex once -> Hamiltonian Path. Each word is connected to every other word (with variable weights) -> Complete Graph. Good news. This problem is well known. :) Bad news. It is NP-Complete. :( researchgate.net/publication/…
– Mark Wistrom
Aug 10 at 14:39






@SaiBot given a similar problem like this in coding interview to finish in 1 hour. I wasn't sure if what I had is the optimal solution. Wanted to hear the thoughts of the others if I am missing anything.
– Kar
Aug 10 at 16:11





You say you were given a "similar" problem in a coding interview, but probably that problem is not similar at all, because it has a good solution that you could code in an hour. This one does not
– Matt Timmermans
Aug 10 at 16:47





@MattTimmermans I didn't want to mention that this was given as is in the coding interview. Now I just did.
– Kar
Aug 11 at 1:18









By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

Popular posts from this blog

Firebase Auth - with Email and Password - Check user already registered

Dynamically update html content plain JS

Creating a leaderboard in HTML/JS