---
# System prepended metadata

title: Algorithms question

---

# Algorithms question
## Question
We define the `edit_distance` function on two strings to be the minimum number of substitutions, additions and removals of characters to get from the first string to the second.

For example
- `edit_distance("hello", "hallo") == 1`
- `edit_distance("hi", "hey") == 2`
- `edit_distance("ab", "ba") == 2`
- `edit_distance("xhello world", "hello world") == 1`
- `edit_distance("hello world", "xhello world") == 1`
- `edit_distance("xhello world", "hello worldx") == 2`
- `edit_distance("abc", "") == 3`

Describe an algorithm for computing the `edit_distance` function.

## Solution

fn cmp(v1, v2, counter):
    
    if len(v1) == 0 { return counter }
    
    
    if first_letter == v2[0] {
        cmp(v1[1:], v2[1:])
    } else {
    
        counter++
        
        substitution_case = cmp(v1[1:], v2[1:])
        add_case = cmp(v1[1:], v2)
        remove_case = cmp(v1, v2[1:])
        
    }
    
    
cmp(5,5)
    cmp(4,4)
        cmp(3,3)
        cmp(4,3)
        cmp(3,4)
    cmp(4,5)
        cmp(3,4)
        cmp()
    cmp(5,4)