Questions tagged [edit-distance]

A class of problems concerned with finding or minimizing the sequence of change operations (such as insertion, deletion, substitution, or transposition) to convert one list or string into another

Filter by
Sorted by
Tagged with
5
votes
2answers
3k views

Speed up a program to find the minimum Hamming distance

I have a solution to the puzzle at https://kattis.csc.kth.se/problem?id=codes. What can I do to make my algorithm much much faster? What the algorithm does is take an N×K matrix and search for the ...
1
vote
3answers
1k views

Using Levenstein distance to compare strings

My overall challenge and why this code was written was to compare two strings. One string being a description of a item in inventory and one string being a description of a item, but possibly ...
2
votes
1answer
542 views

Write a typo correction program with Levenshtein distance algorithm

I'm building a typo correction program. This is the function, which compute the levenshtein distance between two words (a dictionnary word and an input word). I will call this function many times, so ...
2
votes
2answers
7k views

Comparing long lists of strings for the closest match

What's the fastest (quality is important too, but a little less important) way to compare two strings? I'm looking for the most efficient way to compare two strings. Some of the strings I'm comparing ...
8
votes
2answers
11k views

Edit Distance Between Two Strings

...
1
vote
1answer
125 views

“Causes” Puzzle solution (network of words with Levenshtein distance 1)

The "Causes" puzzle is to recursively find, starting with the word "causes", the number of words that can be formed by substituting one letter. ...
2
votes
3answers
815 views

Finding social network of a friend

Following is the code which finds the social network of a friend (i.e. friends of friends and so on). Friends definition is, ff W1 is friend of W2, then there should be Levenshtein distance equal to 1....