package Ġrecursion Ċ Ċ val Ġsquares : ĠMutable List < Mutable List < String >> Ġ= Ġmutable ListOf () Ċ Ċ data Ġclass ĠT rie Node ( val Ġchildren : ĠMutable Map < Char , ĠT rie Node >) Ċ val Ġroot Ġ= ĠT rie Node ( mutable Map Of ()) Ċ Ċ fun Ġtraverse ( square : ĠMutable List < String >, Ġcur : ĠT rie Node , Ġword : ĠStringBuilder , Ġwords : ĠArray < String >) Ġ{ ĊĠĠĠ Ġif Ġ( word . length Ġ== Ġwords [ 0 ]. length ) Ġ{ ĊĠĠĠĠĠĠĠ Ġsquare . add ( word . toString ()) ĊĠĠĠĠĠĠĠ Ġsearch ( square , Ġwords ) ĊĠĠĠĠĠĠĠ Ġsquare . remove At ( square . last Index ) ĊĠĠĠ Ġ} ĊĊĠĠĠ Ġfor Ġ( entry Ġin Ġcur . children . entries ) Ġ{ ĊĠĠĠĠĠĠĠ Ġword . append ( entry . key ) ĊĠĠĠĠĠĠĠ Ġtraverse ( square , Ġentry . value , Ġword , Ġwords ) ĊĠĠĠĠĠĠĠ Ġword . delete Char At ( word . last Index ) ĊĠĠĠ Ġ} Ċ } Ċ Ċ fun Ġsearch ( square : ĠMutable List < String >, Ġwords : ĠArray < String >) Ġ{ ĊĠĠĠ Ġval Ġn Ġ= Ġsquare . size ĊĊĠĠĠ Ġif Ġ( square . size Ġ== Ġwords [ 0 ]. length ) Ġ{ ĊĠĠĠĠĠĠĠ Ġsquares . add ( ArrayList ( square )) ĊĠĠĠĠĠĠĠ Ġreturn ĊĠĠĠ Ġ} ĊĊĠĠĠ Ġ// Ġfollowing Ġtries Ġfor Ġfinding Ġthe Ġgiven Ġprefix Ġof Ġn Ġcharacters ĊĠĠĠ Ġvar Ġcur Ġ= Ġroot ĊĠĠĠ Ġval Ġsb Ġ= ĠStringBuilder () ĊĠĠĠ Ġfor Ġ( i Ġin Ġ 0 Ġuntil Ġn ) Ġ{ ĊĠĠĠĠĠĠĠ Ġif Ġ( square [ i ][ n ] Ġin Ġcur !!. children ) Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠ Ġsb . append ( square [ i ][ n ]) ĊĠĠĠĠĠĠĠĠĠĠĠ Ġcur Ġ= Ġcur . children [ square [ i ][ n ]] !! ĊĠĠĠĠĠĠĠ Ġ} Ġelse Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠ Ġbreak ĊĠĠĠĠĠĠĠ Ġ} ĊĠĠĠ Ġ} ĊĊĠĠĠ Ġ// Ġtra ver sing Ġthe Ġrest Ġof Ġthe Ġtrie Ġsince Ġall Ġwords Ġfit ĊĠĠĠ Ġif Ġ( sb . length Ġ== Ġn ) Ġ{ ĊĠĠĠĠĠĠĠ Ġtraverse ( square , Ġcur , Ġsb , Ġwords ) ĊĠĠĠ Ġ} Ċ } Ċ Ċ // O ( m ^ n ) Ċ fun Ġword S quares ( words : ĠArray < String >): ĠList < List < String >> Ġ{ ĊĊĠĠĠ Ġfor ( word Ġin Ġwords ) Ġ{ ĊĠĠĠĠĠĠĠ Ġvar Ġcur Ġ= Ġroot ĊĠĠĠĠĠĠĠ Ġfor Ġ( ch Ġin Ġword ) Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠ Ġif Ġ( ch Ġ! in Ġcur . children ) Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġcur . children [ ch ] Ġ= ĠT rie Node ( mutable Map Of ()) ĊĠĠĠĠĠĠĠĠĠĠĠ Ġ} ĊĠĠĠĠĠĠĠĠĠĠĠ Ġcur Ġ= Ġcur . children [ ch ] !! ĊĠĠĠĠĠĠĠ Ġ} ĊĠĠĠ Ġ} ĊĊĠĠĠ Ġsearch ( ArrayList ( words [ 0 ]. length ), Ġwords ) ĊĠĠĠ Ġreturn Ġsquares Ċ } Ċ Ċ fun Ġmain () Ġ{ ĊĠĠĠ Ġprintln ( word S quares ( array Of (" area "," lead "," wall "," lad y "," ball "))) Ċ } Ċ