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


Describe an algorithm for computing the `edit_distance` function.

## Solution

```rust=
fn edit_distance(a: &str, b: &str) -> usize {
    if a.len() == 0 && b.len() == 0 {
        0
    } else if a.len() == 0 {
        b.len()
    } else if b.len() == 0 {
        a.len()
    } else if a[0] == b[0] {
        edit_distance(a + 1, b + 1)
    } else {
        1 + min(
            edit_distance(a + 1, b),
            edit_distance(a, b + 1),
            edit_distance(a + 1, b + 1)
        )
    }
}
```

hello, hallo
ello, allo
llo, allo
ello, llo
llo, llo