# 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

fn edit_distance(s1: String, s2: String) -> int {
    let scores = [][];
    
    for s1_index, s1_char in s1.chars().enumerate() {
        for s2_index, s2_char in s2.chars().enumerate() {
            let substitution = scores[s1_index - 1][s2_index - 1];
            let substituion_score = if s1_char == s2_char {
                substitution
            } else {
                substitution + 1
            };
            let deletion_score = scores[s1_index - 1][s2_index];
            let insertion_score = scores[s1_index][s2_index - 1];
            
            let score = min(substition_score, deleteion_score, insertion_score);
            scores[s1_index][s2_index] = score;
        }
    }
    
    scores[s1_len][s2_len];
}