# 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: &str, s2: &str) -> usize {
    let mut result = 0;
    let mut i1 = 0;
    let mut i2 = 0;
    
    loop {
        // find the equivalent block
        while s1.char[i1] == s2.char[i2] {        
            i1 += 1;
            if i1 > s1.len() {
                return result + s2.len - i2;
            }
            i2 += 1;
            if i2 > s2.len() {
                return result + s1.len - i1;
            }
        }
        // find the shorter difference
        let contrib1 = {
            // - 1
            let i1 = i1;
            let mut contrib1 = 0;
            let c2 = s2[i2];
            while s1.char[i1] != c2 {
                i1 += 1;
                if i1 > s1.len {
                    break contrib1 + s2.len - i2;
                }
                contrib1 += 1;
            }
        }
        let contrib2 = {
            // - 2
            let i2 = i2;
            let mut contrib2 = 0;
            let c1 = s1[i1];
            while s2.char[i2] != c1 {
                i2 += 1;
                if i2 > s2.len {
                    break contrib2 + s1.len - i1;
                }
                contrib2 += 1;
            }
        }
        if contrib1 < contrib2 {
            result += contrib1;
            i1 += contrib1;
        } else {
            result += contrib2;
            i2 += contrib2;
        }
        
    }
    result
}