---
# 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("hello world", "xhello world") == 1`
- `edit_distance("hello world", "hello x world") == 2`
- `edit_distance("hello worldx", "xhello world") == 2`
- `edit_distance("abc", "") == 3`

aaaa, bbbb
    aaa, bbbb
     aaa, bbb
    aaa, bbb
    aaaa, bbb

## Solution

fn edit_distance_rec(s1, s2)
start - compare intitial strings, char by char until different
    -- it all match -- return 0
    -- of one side empty -> return larger len

    
    -- it no match
        let result = 1 +  min of (
            remove .. recursive call on (s1, s2[1..])
            subst ..  recursive call on (s1[1..], s2[1..])
            add .. recursive call on (s1[1..], s2)
            
        )
        return result
            

- `edit_distance("hello world", "hello x world uytra") == 2`
- `edit_distance("world", "x world uytra") `
edit_distance("world", "x world uytra") `
edit_distance("world", " world uytra") `
edit_distance("world", "world uytra") `
edit_distance("", "uytra") `

- - `edit_distance("", "uytra") `


- `edit_distance("world", "x world uytra") == 2`


