package Ġde . kotlin cook . text mining Ċ Ċ import Ġjava . lang . Math . max Ċ import Ġjava . util . HashMap Ċ Ċ /** Ċ Ġ* ĠThe ĠD amera u - Le vens ht ein ĠAlgorithm Ġis Ġan Ġextension Ġto Ġthe ĠLe vens ht ein Ċ Ġ* ĠAlgorithm Ġwhich Ġsolves Ġthe Ġedit Ġdistance Ġproblem Ġbetween Ġa Ġsource Ġstring Ġand Ċ Ġ* Ġa Ġtarget Ġstring Ġwith Ġthe Ġfollowing Ġoperations : Ċ Ġ* Ċ Ġ* ĠCharacter ĠInsert ion Ċ Ġ* ĠCharacter ĠDe letion Ċ Ġ* ĠCharacter ĠRe placement Ċ Ġ* ĠAd jacent ĠCharacter ĠSwap Ċ Ġ* Ċ Ġ* ĠNote Ġthat Ġthe Ġadjacent Ġcharacter Ġswap Ġoperation Ġis Ġan Ġedit Ġthat Ġmay Ġbe Ċ Ġ* Ġapplied Ġwhen Ġtwo Ġadjacent Ġcharacters Ġin Ġthe Ġsource Ġstring Ġmatch Ġtwo Ġadjacent Ċ Ġ* Ġcharacters Ġin Ġthe Ġtarget Ġstring , Ġbut Ġin Ġreverse Ġorder , Ġrather Ġthan Ġa Ċ Ġ* Ġgeneral Ġallow ance Ġfor Ġadjacent Ġcharacter Ġsw aps . Ċ Ġ* Ċ Ġ* ĠThis Ġimplementation Ġallows Ġthe Ġclient Ġto Ġspecify Ġthe Ġcosts Ġof Ġthe Ġvarious Ċ Ġ* Ġedit Ġoperations Ġwith Ġthe Ġrestriction Ġthat Ġthe Ġcost Ġof Ġtwo Ġswap Ġoperations Ċ Ġ* Ġmust Ġnot Ġbe Ġless Ġthan Ġthe Ġcost Ġof Ġa Ġdelete Ġoperation Ġfollowed Ġby Ġan Ġinsert Ċ Ġ* Ġoperation . ĠThis Ġrestriction Ġis Ġrequired Ġto Ġpre clude Ġtwo Ġsw aps Ġinvol ving Ġthe Ċ Ġ* Ġsame Ġcharacter Ġbeing Ġrequired Ġfor Ġoptimal ity Ġwhich , Ġin Ġturn , Ġenables Ġa Ġfast Ċ Ġ* Ġdynamic Ġprogramming Ġsolution . Ċ Ġ* Ċ Ġ* ĠThe Ġrunning Ġtime Ġof Ġthe ĠD amera u - Le vens ht ein Ġalgorithm Ġis ĠO ( n * m ) Ġwhere Ġn Ċ Ġ* Ġis Ġthe Ġlength Ġof Ġthe Ġsource Ġstring Ġand Ġm Ġis Ġthe Ġlength Ġof Ġthe Ġtarget Ċ Ġ* Ġstring . ĠThis Ġimplementation Ġconsume s ĠO ( n * m ) Ġspace . Ċ Ġ* Ċ Ġ* Ġ@ author ĠKevin ĠL . Ġand ĠJo erg ĠV oll mer Ġ( Java Cook Ġ& ĠKotlin Cook ) Ċ Ġ* Ġ@ param Ġdelete Cost Ġthe Ġcost Ġof Ġdeleting Ġa Ġcharacter . Ċ Ġ* Ġ@ param Ġinsert Cost Ġthe Ġcost Ġof Ġinserting Ġa Ġcharacter . Ċ Ġ* Ġ@ param Ġreplace Cost Ġthe Ġcost Ġof Ġreplacing Ġa Ġcharacter . Ċ Ġ* Ġ@ param Ġswap Cost Ġthe Ġcost Ġof Ġsw apping Ġtwo Ġadjacent Ġcharacters . Ċ Ġ*/ Ċ class ĠD amera u Le vens ht ein ( private Ġval Ġdelete Cost : ĠInt , ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġprivate Ġval Ġinsert Cost : ĠInt , ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġprivate Ġval Ġreplace Cost : ĠInt , ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġprivate Ġval Ġswap Cost : ĠInt ) Ġ{ ĊĠĠĠ Ġinit Ġ{ ĊĠĠĠĠĠĠĠ Ġcheck ( delete Cost Ġ>= Ġ 0 ) ĊĠĠĠĠĠĠĠ Ġcheck ( insert Cost Ġ>= Ġ 0 ) ĊĠĠĠĠĠĠĠ Ġcheck ( replace Cost Ġ>= Ġ 0 ) ĊĠĠĠĠĠĠĠ Ġcheck ( swap Cost Ġ>= Ġ 0 ) ĊĠĠĠĠĠĠĠ Ġcheck ( 2 Ġ* Ġswap Cost Ġ>= Ġinsert Cost Ġ+ Ġdelete Cost ) ĊĠĠĠ Ġ} ĊĊĠĠĠ Ġ/** ĊĠĠĠĠ Ġ* ĠCompute Ġthe ĠD amera u - Le vens ht ein Ġdistance Ġbetween Ġthe Ġspecified Ġsource ĊĠĠĠĠ Ġ* Ġstring Ġand Ġthe Ġspecified Ġtarget Ġstring . ĊĠĠĠĠ Ġ*/ ĊĠĠĠ Ġfun Ġcompute ( source : ĠString , Ġtarget : ĠString ): ĠInt Ġ{ ĊĠĠĠĠĠĠĠ Ġif Ġ( source . isEmpty ()) Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠ Ġreturn Ġtarget . length Ġ* Ġinsert Cost ĊĠĠĠĠĠĠĠ Ġ} ĊĠĠĠĠĠĠĠ Ġif Ġ( target . isEmpty ()) Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠ Ġreturn Ġsource . length Ġ* Ġdelete Cost ĊĠĠĠĠĠĠĠ Ġ} ĊĠĠĠĠĠĠĠ Ġval Ġtable Ġ= ĠArray ( source . length ) Ġ{ ĠInt Array ( target . length ) Ġ} ĊĠĠĠĠĠĠĠ Ġval Ġsource Index By Character Ġ= ĠHashMap < Char , ĠInt >() ĊĠĠĠĠĠĠĠ Ġif Ġ( source [ 0 ] Ġ!= Ġtarget [ 0 ]) Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠ Ġtable [ 0 ][ 0 ] Ġ= ĠMath . min ( replace Cost , Ġdelete Cost Ġ+ Ġinsert Cost ) ĊĠĠĠĠĠĠĠ Ġ} ĊĠĠĠĠĠĠĠ Ġsource Index By Character . put ( source [ 0 ], Ġ 0 ) ĊĠĠĠĠĠĠĠ Ġfor Ġ( i Ġin Ġ 1 Ġuntil Ġsource . length ) Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠ Ġval Ġdelete Distance Ġ= Ġtable [ i Ġ- Ġ 1 ][ 0 ] Ġ+ Ġdelete Cost ĊĠĠĠĠĠĠĠĠĠĠĠ Ġval Ġinsert Distance Ġ= Ġ( i Ġ+ Ġ 1 ) Ġ* Ġdelete Cost Ġ+ Ġinsert Cost ĊĠĠĠĠĠĠĠĠĠĠĠ Ġval Ġmatch Distance Ġ Ġ= Ġi Ġ* Ġdelete Cost Ġ+ Ġif Ġ( source [ i ] Ġ== Ġtarget [ 0 ]) Ġ 0 Ġelse Ġreplace Cost ĊĠĠĠĠĠĠĠĠĠĠĠ Ġtable [ i ][ 0 ] Ġ= Ġint ArrayOf ( delete Distance , Ġinsert Distance , Ġmatch Distance ). min () !! ĊĠĠĠĠĠĠĠ Ġ} ĊĠĠĠĠĠĠĠ Ġfor Ġ( j Ġin Ġ 1 Ġuntil Ġtarget . length ) Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠ Ġval Ġdelete Distance Ġ= Ġtable [ 0 ][ j Ġ- Ġ 1 ] Ġ+ Ġinsert Cost ĊĠĠĠĠĠĠĠĠĠĠĠ Ġval Ġinsert Distance Ġ= Ġ( j Ġ+ Ġ 1 ) Ġ* Ġinsert Cost Ġ+ Ġdelete Cost ĊĠĠĠĠĠĠĠĠĠĠĠ Ġval Ġmatch Distance Ġ= Ġj Ġ* Ġinsert Cost Ġ+ Ġif Ġ( source [ 0 ] Ġ== Ġtarget [ j ]) Ġ 0 Ġelse Ġreplace Cost ĊĠĠĠĠĠĠĠĠĠĠĠ Ġtable [ 0 ][ j ] Ġ= Ġint ArrayOf ( delete Distance , Ġinsert Distance , Ġmatch Distance ). min () !! ĊĠĠĠĠĠĠĠ Ġ} ĊĠĠĠĠĠĠĠ Ġfor Ġ( i Ġin Ġ 1 Ġuntil Ġsource . length ) Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠ Ġvar Ġmax Source Letter Match Index Ġ= Ġif Ġ( source [ i ] Ġ== Ġtarget [ 0 ]) Ġ 0 Ġelse Ġ- 1 ĊĠĠĠĠĠĠĠĠĠĠĠ Ġfor Ġ( j Ġin Ġ 1 Ġuntil Ġtarget . length ) Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġval Ġcandidate Swap Index : Int ? Ġ= Ġsource Index By Character [ target [ j ]] ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġval Ġj Swap Ġ= Ġmax Source Letter Match Index ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġval Ġdelete Distance Ġ= Ġtable [ i Ġ- Ġ 1 ][ j ] Ġ+ Ġdelete Cost ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġval Ġinsert Distance Ġ= Ġtable [ i ][ j Ġ- Ġ 1 ] Ġ+ Ġinsert Cost ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġvar Ġmatch Distance Ġ= Ġtable [ i Ġ- Ġ 1 ][ j Ġ- Ġ 1 ] ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġif Ġ( source [ i ] Ġ!= Ġtarget [ j ]) Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġmatch Distance Ġ+= Ġreplace Cost ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġ} Ġelse Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġmax Source Letter Match Index Ġ= Ġj ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġ} ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġvar Ġswap Distance Ġ= Ġ ĠInteger . MAX _ VALUE ; ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġif Ġ( candidate Swap Index Ġ!= Ġnull Ġ&& Ġj Swap Ġ!= Ġ- 1 ) Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġswap Distance Ġ= Ġ 0 ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġif Ġ( candidate Swap Index Ġ> Ġ 0 Ġ|| Ġj Swap Ġ> Ġ 0 ) Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġswap Distance Ġ= Ġtable [ max ( 0 , Ġcandidate Swap Index Ġ- Ġ 1 )][ max ( 0 , Ġj Swap Ġ- Ġ 1 )] ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġ} ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġswap Distance Ġ+= Ġ( i Ġ- Ġcandidate Swap Index Ġ- Ġ 1 ) Ġ* Ġdelete Cost ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġswap Distance Ġ+= Ġ( j Ġ- Ġj Swap Ġ- Ġ 1 ) Ġ* Ġinsert Cost Ġ+ Ġswap Cost ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġ} ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġtable [ i ][ j ] Ġ= Ġint ArrayOf ( delete Distance , Ġinsert Distance , Ġmatch Distance , Ġswap Distance ). min () !! ĊĠĠĠĠĠĠĠĠĠĠĠ Ġ} ĊĠĠĠĠĠĠĠĠĠĠĠ Ġsource Index By Character . put ( source [ i ], Ġi ) ĊĠĠĠĠĠĠĠ Ġ} ĊĠĠĠĠĠĠĠ Ġreturn Ġtable [ source . length Ġ- Ġ 1 ][ target . length Ġ- Ġ 1 ] ĊĠĠĠ Ġ} Ċ }