# 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

107 questions
Filter by
Sorted by
Tagged with
371 views

### Edit distance implementation

This problem is taken from the book Introduction to Algorithms, Third Edition By Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest and Clifford Stein: In order to transform one source string ...
3k views

### Check if two strings are one 'edit' apart using Python

The code below is my solution in python 3 to exercise 1.5 in Cracking the Coding Interview. I would appreciate feedback on both the algorithm (improvements to space and time complexity) and/or coding ...
150 views

### Efficiently calculating differences between file using diff file

I'm using SVNKit to get diff information between two revisions. I'm using the diff utility to generate a diff file, however I still need to parse it into numbers. I implemented a solution, but it is ...
1k views

### Matlab implementation of Needleman-Wunsch algorithm

This code (an implementation of the path finding Needleman-Wunsch algorithm), given two sequences, correctly aligns and calculates the similarity of them. For example, given two sequences: AAA,CCC ...
7k views

### A String.prototype.diff() implementation (text diff)

I just had the idea to develop an algorithm to calculate and highlight the difference between two strings. I know that there are already some libraries to do the job but I just tried to make my own. I ...
1k views

### Clustering nodes with Hamming distance < 3

I want to speed up the following code, which is from an algorithm class. I get a list of 200000 nodes where every node is a tuple of the length of 24 where every item is either a 1 or 0. These ...
563 views

### Hamming distance in Scala

Problem Write a program that can calculate the Hamming difference between two DNA strands. GAGCCTACTAACGGGAT CATCGTAATGACGGCCT ^ ^ ^ ^ ^ ^^ Code ...
2k views

### Making as many unique strings as possible by removing two characters

I'm attempting a programming challenge type task in C#, where the goal is to determine how many unique strings can be obtained by removing two characters. The prompt for the task implied that I should ...
130 views

### Name-deduplicating class

Recently I asked a question on Programming SE about public vs private methods fo unit testing, which generated a lot of interesting responses. I only posted a skeleton of the code there, as it was a ...
81 views

### A sequence of mistakes

This question is part of a series solving the Rosalind challenges. For the previous question in this series, see The Genetic Code. The repository with all my up-to-date solutions so far can be found ...
870 views

### Calculate the Hamming difference between two DNA strands

Write a program that can calculate the Hamming difference between two DNA strands. GAGCCTACTAACGGGAT CATCGTAATGACGGCCT ^ ^ ^ ^ ^ ^^ The Hamming distance between these two DNA ...
2k views

### Levenshtein distance with edit sequence and alignment in Java

I have this program that computes a Levenshtein distance of the two input strings, their edit sequence, and the alignment: LevenshteinEditDistance.java: ...
341 views

### Making the Levenshtein distance code cleaner

I was writing an implementation of Levenshtein distance in Python and I found my code really ugly. Have you any idea how to make it more elegant? ...
4k views

### Comparing two approximate string matching algorithms in Java

Problem description Given a text $T[0..n)$, a pattern $P[0..m)$, and a nonnegative integer $k$, report all positions $j \in [0..n)$ such that $ed(P, T(j - l..j]) \leq k$ for some \\$l \geq 0\...
250 views

### Duplicate Line Finder

I recently wrote a program that reads a plain text file, and compares every line and alerts you if any are similar, based on a float value that you pass in to a function. ...
282 views

### String similarity calculation

For string similarity, it is defined as longest common prefix length. For example, "abc" and "abd" is 2, and "aaa" and "aaab" is 3. The problem is calculate the similarity of string S and all its ...
218 views

### Comparison function for strings

I got a function that has as input 2 strings, computes the string similarity of all the combinations and give back and output the highest similarity. For example, "you are" and "are you" will have 1 ...
845 views

### Find no of swaps needed to club identical elements of array together

I have created a solution for the problem as below: Given a string S consisting of letters 'O' and 'Z'. Calculate the minimum number of changes required such that all O's are adjacent to each ...
1k views

### Jaccard distance between strings in Rust

The Jaccard distance between two sets is the size of their intersection divided by the size of their union. For example, the distance between {1, 2, 3} and ...
167 views

### Iterate over large amount of words in Python

I wrote a program that should check a dictionary that contains about 50000 other dictionaries. In those dictionaries, one of the keys has a list of words as value. Now, I iterate over those words, ...
10k views

### Algorithm to transform one word to another through valid words

I have been practicing backtracking and I wanted to know how I can improve my code. For eg, I don't want to use global. Also, I am not sure if my code will work for all the cases. ...
224 views

### Wagner-Fischer algorithm

Please let me know if there is any other optimal way of doing this. ...
955 views

### Approximately matching strings to elements in an array

I have two datasets: A list containing about 4200 string elements A list containing about 119,000 string elements I'm taking each element from list 1 and looping through each element in list 2 using ...
157 views

### Recognizing a sequence read through OCR software

I am trying to recognize a sentence that I have read through optical character recognition software. This code will eventually run on a Raspberry Pi. I know for certain that it's meant to be one of a ...
2k views

### Count chars difference between two strings

Given two strings with the same length, we check how many chars on the same positions are different. For example: ABCD and ABBD should return 1. Here is a link to a gist with tests, to have a better ...
210 views

### Console app to compare all directory names for similarity

I just got the urge to write a small console app to compare all directories name for similarity. I have > 3000 directories and over time some of them are really similar, eg. an update: Test Case ver 1 ...
2k views

### Change one word into another by picking words that differ by one character

There is a file with two words with the same length. Call them first and last. Also there is a file - dictionary with a lot of different words. The task is to find shortest chain of words from ...
139 views

### Levenshtein Distance with Haskell Vectors and Memoization

Is the following an effective way to implement the Levenshtein Distance with Haskell vectors? ...
731 views

### Word ladder solution in Java using matrix

Given two words (start and end), and a dictionary, find the length of shortest transformation sequence from start to end, such that only one letter can be changed at a time and each intermediate word ...
270 views

I wrote a program that calculates the minimum number of rungs of a "word ladder" between a starting word and an ending word. The function minlinks() takes in 3 ...
4k views

### Edit distance between 2 strings

I have written a program that calculates the "cost" of transforming one string into another. I would like you to review it. ...
2k views

### Sorting movie search results by similarity

I want to sort "movie search results" to get most probable movie that match "search". Input example: CARS.2.2011.720P.AC3.mkv I have a NameMatcher class ...
1k views

### Image similarity measure

I'm attempting to speed up my genetic algorithm that modifies images. After searching, I've found that my fitness function is the bottleneck, taking sometimes up to ...
92 views

### Find files with similar contents

I'm not normally a C programmer but thought I'd take a shot at making something useful. This is a C utility I wrote to judge how similar several files are using the algorithm I think ...
265 views

### Finding the minimum number of required deletions to have a non-repeating string

I wrote code for the following problem: Given a string, print out the number of deletions required so that the adjacent alphabets are distinct. Please suggest different methods by which I can ...
12k views

### One character diff - string comparison

The question was: Create an algorithm to check if two strings differ by one character. This wasn't my interview, so I tried to understand the question. Options: just compare the chars one by one,...
1k views

### Parsing URLs in Pandas DataFrame

My client needs their Google AdWords destination URL query parsed and the values spell checked to eliminate any typos ("use" instead of "us", etc). I'm pulling the data using the AdWords API and ...
3k views

This is a LeetCode problem called Word Ladder: Given two words (start and end), and a dictionary, find the length of shortest transformation sequence from start to end, where only one letter can ...
1k views

### Basic T-SQL to compare two same length strings

I've come up with the following T-SQL to compare similar same length strings. Example usage would be: OCR returns a value which is expected to be in the database. PATINDEX is used to check the value'...
651 views

### Python code for detecting a single item moved in a list

I need to write a function that takes an original list of unique values and a resulting list: [0,1,2,3] [0,3,1,2] and detect that only a single element was moved ...
2k views

### The Love-Letter Mystery

Problem Statement James got hold of a love letter that his friend Harry has written for his girlfriend. Being the prankster that James is, he decides to meddle with it. He changes all the words ...
803 views

### Python softmatcher using difflib impracticably slow

I have a softmatch function (below) that takes a donor list and a new entry and looks to see if the given donor already exists. The data is not exact, so I have to use a softmatch to determine ...
1k views

### Finding the best matching block/patch in Python

I wish to locate the closest matching NxN block within a WxW window centred at location (x,y) of a larger 2D array. The code below works fine but is very slow for my needs as I need to run this ...
702 views

### Comparing client lists with Cross Joins

I've written a query to compare the clients in our database with the people in a list that I've received. It needs to check if anyone from the list is one of our clients. I've created a temporary ...
1k views

### Simple fuzzy text search algorithm

Basically, this code takes a keyword and an array of strings, then sorts them based on two things: the number of characters shared with the key, and the distance between them.(As a side note, would ...
19k views

### String Matching and Clustering

I have a pretty simple problem. A large set of unique strings that are to various degrees not clean, and in reality they in fact represent the same underlying reality. They are not person names, but ...
704 views

### “Edit distance” UVA programming challenge

I'm trying to solve a programming challenge for fun. The programming challenge is here and my solution for the same can be found here. It currently causes an exceeded time limit. ...
495 views

### Is this the most efficient way to track word changes in a string?

I'm working on a writing platform and am using a modified version of the Levenshtein distance algorithm to track a writer's engagement with their writing. It tracks not only words added to their ...