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

## Solution

ed("aa", "bb")
    ed("a", "b")
    ed("aa", "b")
        ed("a", "b")
    ed("a", "bb")
        ed("a", "b")

```rust
fn edit_distance(s1: &str, s2: &str) -> usize {        
    if s1.is_empty() || s2.is_empty() {
        return s1.len().max(s2.len());
    }
    
    if s1[0] == s2[0] {
        return 0 + edit_distance(s1[1..], s2[1..]);
    }

    let added_distace = edit_distance(s1[1..], s2[0..]) + 1;
    let removed_distance = edit_distance(s1[0..], s2[1..]) + 1;
    let subbed_distance = edit_distance(s1[1..], s2[1..]) + 1;
    
    added_distance.min(removed_distance).min(subbed_distance)
}
```
