This problem is taken from the book Introduction to Algorithms, Third Edition By Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest and Clifford Stein:In order to transform one source string of text x[1..m] to a target  string y[1..n], we can perform various transformation operations.  Our goal is, given x and y, to produce a series of transformations  that change x to y. We use an array  zassumed to be large enough to  hold all the characters it will needto hold the intermediate results.  Initially, z is empty, and at termination, we should have z[j] = y[j]   for j = 1, 2,..., n. We maintain current indices i into x and j into  z, and the operations are allowed to alter z and these indices.  Initially, i = j = 1. We are required to examine every character in x  during the transformation, which means that at the end of the sequence  of transformation operations, we must have i = m + 1.We may choose from among six transformation operations:Copy a character from x to z by setting  z[j] = x[i] and then incrementing both i and j. This operation examines x[i].Replace a character from x by another character c, by setting z[j] = c, and then incrementing both i and j . This operation examines x[i].Delete a character from x by incrementing i but leaving j alone. This operation examines x[i].Insert the character c into z by setting z[j] = c and then incrementing j , but leaving i alone. This operation examines no  characters of x.Twiddle (i.e., exchange) the next two characters by copying them from x to z but in the opposite order; we do so by setting z[j] = x[i+ 1] and  z[j + 1] = x[i] and then setting i = i + 2 and j = j + 2. This operation examines x[i] and x[i + 1].Kill the remainder of x by setting i = m + 1. This operation examines all characters in x that have not yet been examined. This  operation, if performed, must be the final operation.a. Given two sequences x[1..m] and y[1..n] and set of transformation  operation costs, the edit distance from x to y is the cost of the  least expensive operation sequence that transforms x to y. Describe a  dynamic-programming algorithm that finds the edit distance from  x[1..m] to y[1..n] and prints an optimal operation sequence. Analyze  the running time and space requirements of your algorithmMy solution is \$O(nm + m+n)\$.Code:extern crate rand;use std::collections::HashMap;use std::collections::VecDeque;#[derive(Debug, Copy, Clone, PartialEq, Eq, Hash)]enum EditOp {    Copy,    Replace,    Delete,    Insert,    Twiddle,    Kill,}impl EditOp {    fn valid(&self,             i       : usize,             j       : usize,             iprev   : char,             jprev   : char,             icurrent: char,             jcurrent: char) -> bool {        let threshold = |p| i != p || j == p;         match *self {            EditOp::Copy    => threshold(1)                                 && icurrent == jcurrent,            EditOp::Replace => threshold(1),            EditOp::Delete  => i > 1,            EditOp::Twiddle => i > 1 && j > 1                                && threshold(2)                                && icurrent == jprev                                && iprev == jcurrent,            _ => true,                                                                  }    }    fn displacement(&self) -> (usize, usize) {        match *self {            EditOp::Copy    => (1, 1),            EditOp::Replace => (1, 1),            EditOp::Delete  => (1, 0),            EditOp::Insert  => (0, 1),            EditOp::Twiddle => (2, 2),            EditOp::Kill    => (0, 0),            }    }    fn apply(&self,              from_itr: &mut std::str::Chars,              to_itr  : &mut std::str::Chars,              result  : &mut String) {        match *self {            EditOp::Copy    => {                 result.push(from_itr.next().unwrap());                to_itr.next();            },            EditOp::Replace => {                result.push(to_itr.next().unwrap());                from_itr.next();            },            EditOp::Delete  => {                from_itr.next();            },            EditOp::Insert  => {                result.push(to_itr.next().unwrap());            },            EditOp::Twiddle => {                let second = from_itr.next().unwrap();                let first = from_itr.next().unwrap();                result.push(first);                result.push(second);                to_itr.next();                to_itr.next();            },            EditOp::Kill => {},        }    }}fn create_tables(from_len: usize,                  to_len  : usize,                  costs   : &HashMap<EditOp, usize>) -> (Vec<Vec<EditOp>>, Vec<Vec<usize>>) {        let mut op_table   = vec![ vec![EditOp::Kill; to_len]; from_len ];    let mut cost_table = vec![ vec![0usize; to_len]; from_len ];    let delete_cost    = costs.get(&EditOp::Delete).map(|c| *c).unwrap_or(0);    for (i, c) in (1.. from_len).map(|i|(i, i * delete_cost)) {        cost_table[i][0] = c;        op_table[i][0]   = EditOp::Delete;    }     (op_table , cost_table)}fn edit_distance(from : &str,                  to   : &str,                  costs: &HashMap<EditOp, usize>) -> (usize, VecDeque<EditOp>){    if costs.is_empty() {        panic!(map of costs is empty);    }    let from_len = from.chars().count();     let to_len   = to.chars().count();    let (mut op_table, mut cost_table) = create_tables(from_len + 1,                                                        to_len + 1,                                                        costs);    let (mut lasti, mut lastj)         = (' ', ' ');    for (i, ichar) in from.chars().enumerate() {        for (j, jchar) in to.chars().enumerate() {            let (i, j) = (i + 1, j + 1);            let (op, cost) = costs.iter()                .filter(|&(x, _)| !x.eq(&EditOp::Kill))                .filter(|&(x, _)| x.valid(i, j, lasti, lastj,                                           ichar, jchar))                .map(|(x, c)| {                    let (di, dj) = x.displacement();                    (x, cost_table[i - di][j - dj] + c)                })                .min_by_key(|&(_, c)| c)                .unwrap();             cost_table[i][j] = cost;            op_table[i][j] = *op;            lastj = jchar;        }        lasti = ichar;    }    let no_kill_cost    = cost_table[from_len][to_len];    let (i, cost, kill) = costs.get(&EditOp::Kill)                               .map(|kc| min_with_kill(&cost_table,                                                        from_len,                                                        to_len, *kc))                               .unwrap_or((from_len, no_kill_cost, None));    (cost, build_operations(kill, &op_table, i, to_len))}fn edit(from: &str, to: &str, ops: &VecDeque<EditOp>) -> String {       let mut result   = String::new();    let mut from_itr = from.chars();    let mut to_itr   = to.chars();    for op in ops {        op.apply(&mut from_itr, &mut to_itr, &mut result);          }    result}fn min_with_kill(cost_table: &Vec<Vec<usize>>,                  from_size : usize,                  to_size   : usize,                  kill_cost : usize ) -> (usize, usize, Option<EditOp>) {    let no_kill_cost  = cost_table[from_size][to_size];    (1..from_size).map(|i|(i, cost_table[i][to_size] + kill_cost) )                  .map(|(i, c)|(i, c, Some(EditOp::Kill)))                  .chain(Some((from_size, no_kill_cost, None)).into_iter())                  .min_by_key(|&(_, cost, _)| cost).unwrap() }fn build_operations(kill    : Option<EditOp>,                     op_table: &Vec<Vec<EditOp>>,                     i       : usize,                     j       : usize) -> VecDeque<EditOp> {    let itr = std::iter::repeat(()).scan((i, j), |s,_| {            let op       = op_table[s.0][s.1];             let (id, jd) = op.displacement();            *s = (s.0 - id, s.1 - jd);             Some(op)    }).take_while(|op| !op.eq(&EditOp::Kill));    let mut stack = VecDeque::new();    for op in kill.into_iter().chain(itr) {        stack.push_front(op);    }    stack}fn main() { let mut map = HashMap::new();    map.insert(EditOp::Copy, 2);    map.insert(EditOp::Replace, 3);    map.insert(EditOp::Delete, 2);    map.insert(EditOp::Insert, 4);    map.insert(EditOp::Twiddle, 1);    map.insert(EditOp::Kill, 1);    let from = \n\                \n\                \n\                \n\                \n\                \n\                \n\                \n\                \n\                \n\                \n\                \n\                \n\                \n\                \n\                \n\                \n\                \n\                \n\                \n\                \n\                \n\                ;    let to =  //\n\              //\n\              //\n\              |\n\              -\n\              \n\                ;    let (c, s) = edit_distance(&from, &to, &map);      let result = edit(&from, &to, &s);    println!(cost = {}, c);    println!({:?}, s);    println!({}, result);}Test:use rand::Rng;fn random_string(size: usize) -> String {    (0..size).map(|_|rand::random::<char>()).collect()}#[test]fn test_for_accurate_edition(){    let mut map = HashMap::new();    map.insert(EditOp::Copy, 2);    map.insert(EditOp::Replace, 3);    map.insert(EditOp::Delete, 2);    map.insert(EditOp::Insert, 4);    map.insert(EditOp::Twiddle, 1);    map.insert(EditOp::Kill, 1);    let size_generator = || rand::thread_rng().gen_range(100, 500);    for _ in 0..100 {        let from = random_string(size_generator());        let to = random_string(size_generator());        let (_, s) = edit_distance(&from, &to, &map);          let result = edit(&from, &to, &s);        assert_eq!(to, result);               }}
Edit distance implementation
algorithm;rust;dynamic programming;edit distance
Here's a lightweight review...You can combine imports with {}: use std::collections::{HashMap, VecDeque};Consider importing enum variants in methods that exhaustively match on a lot of them. This helps avoid duplication and rightward pushing of code.Accept a generic type that implements an iterator, instead of the specific std::str::Chars.Introduce more and unique types, especially when you have repeated parallel names (i, iprev, icurrent). This also allows you to move functionality into methods.Introduce type aliases. This is a tiny step towards official types, but gives an opportunity to introduce names and shorten them.Instead of VecDeque, use a normal Vec, then you can use Iterator::collect and reverse it.Use a == &b instead of a.eq(&b).I always recommend using expect instead of unwrap. When the panic happens, you will be much happier having some context of where the failure is.Maybe introduce a dedicated struct for the cost mapping. Then you can implement Default, and there's no chance of missing a key.Use &[T] instead of &Vec<T>. Faster and more usable.[Clippy] Combine identical match arms with Foo | Bar.[Clippy] Use map_or instead of map().unwrap_or.[Clippy] Can use cloned instead of |x| *x.[Clippy] Calls to edit and edit_distance have extra references.Check out rustfmt, which, let's say disagrees, with some of your style choices. Unfortunately, I found the code very dense, which made reading over it fairly difficult. It's possible some more verbose names could help. Here's a cherry-picked sample of code that takes a second to mentally process :.map(|(x, c)| {    let (di, dj) = x.displacement();    (x, cost_table[i - di][j - dj] + c)})extern crate rand;use std::collections::HashMap;#[derive(Debug, Copy, Clone, PartialEq, Eq, Hash)]enum EditOp {    Copy,    Replace,    Delete,    Insert,    Twiddle,    Kill,}#[derive(Debug, Copy, Clone)]struct FindBetterName {    idx: usize,    prev: char,    current: char,}impl FindBetterName {    fn valid_twiddle(&self, other: &FindBetterName) -> bool {        self.idx > 1 && other.idx > 1 && self.current == other.prev && self.prev == other.current    }}impl EditOp {    fn valid(&self, i: FindBetterName, j: FindBetterName) -> bool {        use EditOp::*;        let threshold = |p| i.idx != p || j.idx == p;        match *self {            Copy => threshold(1) && i.current == j.current,            Replace => threshold(1),            Delete => i.idx > 1,            Twiddle => threshold(2) && i.valid_twiddle(&j),            _ => true,        }    }    fn displacement(&self) -> (usize, usize) {        use EditOp::*;        match *self {            Copy | Replace => (1, 1),            Delete => (1, 0),            Insert => (0, 1),            Twiddle => (2, 2),            Kill => (0, 0),        }    }    fn apply<F, T>(&self, mut from_itr: F, mut to_itr: T, result: &mut String)        where F: Iterator<Item = char>,              T: Iterator<Item = char>    {        use EditOp::*;        match *self {            Copy => {                result.push(from_itr.next().unwrap());                to_itr.next();            }            Replace => {                result.push(to_itr.next().unwrap());                from_itr.next();            }            Delete => {                from_itr.next();            }            Insert => {                result.push(to_itr.next().unwrap());            }            Twiddle => {                let second = from_itr.next().unwrap();                let first = from_itr.next().unwrap();                result.push(first);                result.push(second);                to_itr.next();                to_itr.next();            }            Kill => {}        }    }}type CostMap = HashMap<EditOp, usize>;fn create_tables(from_len: usize,                 to_len: usize,                 costs: &CostMap)                 -> (Vec<Vec<EditOp>>, Vec<Vec<usize>>) {    let mut op_table = vec![ vec![EditOp::Kill; to_len]; from_len ];    let mut cost_table = vec![ vec![0usize; to_len]; from_len ];    let delete_cost = costs.get(&EditOp::Delete).cloned().unwrap_or(0);    for (i, c) in (1..from_len).map(|i| (i, i * delete_cost)) {        cost_table[i][0] = c;        op_table[i][0] = EditOp::Delete;    }    (op_table, cost_table)}fn edit_distance(from: &str, to: &str, costs: &CostMap) -> (usize, Operations) {    if costs.is_empty() {        panic!(map of costs is empty);    }    let from_len = from.chars().count();    let to_len = to.chars().count();    let (mut op_table, mut cost_table) = create_tables(from_len + 1, to_len + 1, costs);    let (mut lasti, mut lastj) = (' ', ' ');    for (i, ichar) in from.chars().enumerate() {        for (j, jchar) in to.chars().enumerate() {            let (i, j) = (i + 1, j + 1);            let ii = FindBetterName {                idx: i,                prev: lasti,                current: ichar,            };            let jj = FindBetterName {                idx: j,                prev: lastj,                current: jchar,            };            let (op, cost) = costs.iter()                .filter(|&(x, _)| x != &EditOp::Kill)                .filter(|&(x, _)| x.valid(ii, jj))                .map(|(x, c)| {                    let (di, dj) = x.displacement();                    (x, cost_table[i - di][j - dj] + c)                })                .min_by_key(|&(_, c)| c)                .unwrap();            cost_table[i][j] = cost;            op_table[i][j] = *op;            lastj = jchar;        }        lasti = ichar;    }    let no_kill_cost = cost_table[from_len][to_len];    let (i, cost, kill) = costs.get(&EditOp::Kill)        .map_or((from_len, no_kill_cost, None), |kc| {            min_with_kill(&cost_table, from_len, to_len, *kc)        });    (cost, build_operations(kill, &op_table, i, to_len))}type Operations = Vec<EditOp>;type OperationsSlice<'a> = &'a [EditOp];fn edit(from: &str, to: &str, ops: OperationsSlice) -> String {    let mut result = String::new();    let mut from_itr = from.chars();    let mut to_itr = to.chars();    for op in ops {        op.apply(&mut from_itr, &mut to_itr, &mut result);    }    result}fn min_with_kill(cost_table: &[Vec<usize>],                 from_size: usize,                 to_size: usize,                 kill_cost: usize)                 -> (usize, usize, Option<EditOp>) {    let no_kill_cost = cost_table[from_size][to_size];    (1..from_size)        .map(|i| (i, cost_table[i][to_size] + kill_cost))        .map(|(i, c)| (i, c, Some(EditOp::Kill)))        .chain(Some((from_size, no_kill_cost, None)).into_iter())        .min_by_key(|&(_, cost, _)| cost)        .unwrap()}fn build_operations(kill: Option<EditOp>,                    op_table: &[Vec<EditOp>],                    i: usize,                    j: usize)                    -> Operations {    let itr = std::iter::repeat(())        .scan((i, j), |s, _| {            let op = op_table[s.0][s.1];            let (id, jd) = op.displacement();            *s = (s.0 - id, s.1 - jd);            Some(op)        })        .take_while(|op| op != &EditOp::Kill);    let mut stack: Vec<_> = kill.into_iter().chain(itr).collect();    stack.reverse();    stack}fn main() {    let mut cost_map = HashMap::new();    cost_map.insert(EditOp::Copy, 2);    cost_map.insert(EditOp::Replace, 3);    cost_map.insert(EditOp::Delete, 2);    cost_map.insert(EditOp::Insert, 4);    cost_map.insert(EditOp::Twiddle, 1);    cost_map.insert(EditOp::Kill, 1);    let from = \n\                \n\                \n\                \n\                \n\                \n\                \n\                \n\                \n\                \n\                \n\                \n\                \n\                \n\                \n\                \n\                \n\                \n\                \n\                \n\                \n\                \n\                ;    let to =  //\n\              //\n\              //\n\              |\n\              -\n\              \n\                ;    let (c, s) = edit_distance(from, to, &cost_map);    let result = edit(from, to, &s);    println!(cost = {}, c);    println!({:?}, s);    println!({}, result);}