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

Describe an algorithm for computing the `edit_distance` function.

## Solution

fn edit_distance_dp(s1: &str, s2: &str, i1: usize, i2: usize) -> {
    
    //  We exhausted all of our characters
    if i1 >= s1.len() && i2 >= s2.len() {
        return 0;
    } 
    
    // We exhausted all characters of the first string, which means to reach the
    // end string, we need to add all the remaining characters of the second string
    // to our first string
    else if i1 >= s1.len() {
        let remaining = s2.len() - i2;
        return remaining;
    }
    
    // We exhausted all characters of the second string, which means to reach the
    // end string, we need to REMOVE all the remaining characters of the first string
    // from our first string
    else if i2 >= s2.len() {
        let remaining = s1.len() - i1;
        return remaining;
    }
    
    let c1 = s1[i1];
    let c2 = s2[i2];
    
    if c1 != c2 {
        let dist_add = edit_distance_dp(s1, s2, i1 + 1, i2);
        let dist_substitute = edit_distance_dp(s1, s2, i1 + 1, i2 + 1, new_cost);
        let dist_remove = edit_distance_dp(s1, s2, i1, i2 + 1, new_cost);
        
        return std::iter::from(dist_add, dist_sub, dist_remove).min() + 1;
    }
    else {
        return edit_distance_dp(s1, s2, i1 + 1, i2 + 1, distance);
    }
}

fn edit_distance(s1: &str, s2: &str) -> usize
{
    
}