Questions tagged [edit-distance]

Question 1

Input A binary string \$s\$ of length \$n\$ and a positive integer \$k \leq n\$. Output The number of binary strings with Levenshtein distance exactly \$k\$ from the string \$s\$. Example outputs Each ...

Question 2

I have string \$s\$ of length \$n\$ and some constant integer \$k\$ which is at most \$n\$. Give the fastest algorithm to sample a random string with Levenshtein distance \$k\$ from \$s\$ uniformly. ...

Question 3

Given two strings \$A\$ and \$B\$ with edit (Levenshtein) distance \$x\$, find a third string with edit distance \$a\$ to \$A\$ and edit distance \$b\$ to \$B\$ so that \$a+b=x\$ and \$a=int(x/2)\$ (...

Question 4

Inspired by this Your task today: given two strings, find the string with the lowest maximum Levenshtein distance to the input strings. For example, using Steffan ...

Question 5

Take as input two strings \$A\$ and \$B\$. Output a string \$C\$ that is \$A\$ but with two characters swapped such that the Levenshtein distance \$d(C,B)\$ is as small as possible. You must swap ...

Question 6

Given a list of the integers from \$1\$ to some \$n\$, give the minimum number of adjacent swaps required to put the list in ascending order. You will receive a list as input and should output a non-...

Question 7

Your task, at the moment that you choose to accept it, is to write a program that, when given a string and a PCRE-regex, calculates the minimum Levenshtein distance to another string that matches the ...

Question 8

The word "levencycle" is inspired by cyclic levenquine challenge. Definitions A 1-dup permutation of order \$n\$ is some permutation of \$1, \cdots, n\$ plus one duplicate number in the ...

Question 9

This challenge is about the following variant of edit distance. Say we have a cost of 1 for inserts, deletes and substitutions as usual with one exception. A substitution for a given letter ...

Question 10

The Levenshtein distance between two strings is the minimum number of single character insertions, deletions and substitutions needed to transform one string into the other. Let us call insertions, ...

Question 11

The edit distance between two strings is the minimum number of single character insertions, deletions and substitutions needed to transform one string into the other. This task is simply to write ...

Question 12

This is the Robber post. The Cop post is here. Your task is to take an integer input N and output the Nth digit in the sequence OEIS A002942. The sequence consists of the square numbers written ...

Question 13

This is the Cop post. The Robber post is here. Your task is to take an integer input N and output the Nth digit in the sequence OEIS A002942. The sequence consists of the square numbers written ...

Question 14

The Levenshtein edit distance between two strings is the minimum possible number of insertions, deletions, or substitutions to convert one word into another word. In this case, each insertion, ...

Question 15

While there are many edit distance questions, such as this one, there isn't a simple question to write a program that calculates the Levenshtein distance. Some Exposition The Levenshtein edit ...

Stack Exchange Network

Questions tagged [edit-distance]

Count the size of the Levenshtein neighborhood

Pick a random string at a fixed edit distance

Find a string in the middle

Find The Average String Between Two Strings

Find the closest swap

Damerau-Damerau distance

Give the minimum Levenshtein distance to a string that matches the regex

Hamiltonian levencycle of 1-dup permutations

Edit distance where a substitution only costs the first time

Find the min and max number of substitutions

Code golf edit distance 2

Levenshtein distance & OEIS (Robbers)

Levenshtein distance & OEIS (Cops)

Levenshtein Your Source

Levenshtein Distance

Hot Network Questions