# 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`

## Solution

fn edit_distance(left: &str, right: &str) -> usize {
    if len(left) == 0 {
        return len(right);
    }
    if len(right) == 0 {
        return len(left);
    }
    if left[0] == right[0] {
        return edit_distance(&left[1..], &right[1..]);
    }
    return min(
        edit_distance(&left[1..], &right),
        edit_distance(left, &right[1..]),
        edit_distance(&left[1..], &right[1..]),
    ) + 1;
}

let x = 'label: loop {
  break "test";  
};

let x = 'label: {
    if some_condition {
        break 'label "test";
    }
    oeauoaeu
    oeauoaeu
    "not test"
};

extern {
    type X;
}

struct S;

"abc", "xyz"
"bc", "xyz",
"c", "xyz",
"", "xyz",
"bc", "yz",
"c", "yz",
"", "yz",
"bc", "z",
""

O(n * m)