package Ġcom . github . sh atter ed suite . core . algorithm Ċ Ċ import Ġkotlin . math . min Ċ Ċ object ĠMinimum Edit Distance Ġ{ ĊĠĠĠ Ġfun Ġrun ( s 1 : ĠString , Ġs 2 : ĠString ): ĠInt Ġ{ ĊĠĠĠĠĠĠĠ Ġreturn Ġdistance ( s 1 , Ġs 2 ). first ĊĠĠĠ Ġ} ĊĊĠĠĠ Ġfun Ġrun Get Cache ( s 1 : ĠString , Ġs 2 : ĠString ): ĠPair < Int , ĠList < List < Int >>> Ġ{ ĊĠĠĠĠĠĠĠ Ġreturn Ġdistance ( s 1 , Ġs 2 ) ĊĠĠĠ Ġ} ĊĊĠĠĠ Ġprivate Ġfun Ġdistance ( s 1 : ĠString , Ġs 2 : ĠString ): ĠPair < Int , ĠList < List < Int >>> Ġ{ ĊĠĠĠĠĠĠĠ Ġval Ġs 1 Length Ġ= Ġs 1 . length ĊĠĠĠĠĠĠĠ Ġval Ġs 2 Length Ġ= Ġs 2 . length ĊĊĠĠĠĠĠĠĠ Ġval Ġcache Ġ= ĠlistOf ( Mutable List ( s 1 Length ) Ġ{ Ġ 0 Ġ}, ĠMutable List ( s 2 Length ) Ġ{ Ġ 0 Ġ}) ĊĊĠĠĠĠĠĠĠ Ġfor Ġ( i Ġin Ġ 0 .. s 1 Length ) Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠ Ġcache [ 0 ][ i ] Ġ= Ġi ĊĠĠĠĠĠĠĠ Ġ} ĊĊĠĠĠĠĠĠĠ Ġfor Ġ( i Ġin Ġ 1 .. s 2 Length ) Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠ Ġfor Ġ( j Ġin Ġ 0 .. s 1 Length ) Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġcache [ i Ġ% Ġ 2 ][ j ] Ġ= Ġwhen Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġj Ġ== Ġ 0 Ġ-> Ġi ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġs 1 [ j Ġ- Ġ 1 ] Ġ== Ġs 2 [ i Ġ- Ġ 1 ] Ġ-> Ġcache [( i Ġ- Ġ 1 ) Ġ% Ġ 2 ][ j Ġ- Ġ 1 ] ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġelse Ġ-> Ġ 1 Ġ+ Ġmin ( min ( cache [( i Ġ- Ġ 1 ) Ġ% Ġ 2 ][ j ], Ġcache [ i Ġ% Ġ 2 ][ j Ġ- Ġ 1 ]), Ġcache [( i Ġ- Ġ 1 ) Ġ% Ġ 2 ][ j Ġ- Ġ 1 ]) ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġ} ĊĠĠĠĠĠĠĠĠĠĠĠ Ġ} ĊĠĠĠĠĠĠĠ Ġ} ĊĊĠĠĠĠĠĠĠ Ġreturn Ġcache [ s 2 Length Ġ% Ġ 2 ][ s 1 Length ] Ġto Ġcache ĊĠĠĠ Ġ} Ċ }