Problem Statement
In this problem you will be given a
For example, if S = "something", prefix = "awesome", and suffix = "ingenious", than the prefix score of S is 4 (the matched characters are "some") and the suffix score is 3 (the matched characters are "ing").
The match score of a string S with respect to a given template is the sum of its prefix and suffix match scores. Find the non-empty substring of text with the maximal match score according to the template (prefix, suffix). In case of a tie, return the substring with the maximal prefix score. If there are still several candidates, return one that comes first lexicographically.
Definition
- Class:
- TemplateMatching
- Method:
- bestMatch
- Parameters:
- String, String, String
- Returns:
- String
- Method signature:
- String bestMatch(String text, String prefix, String suffix)
- (be sure your method is public)
Notes
- String A comes before string B lexicographically if A is a proper prefix of B, or if A has a smaller character at the first position where the strings differ. When comparing the characters, refer to the following list of characters in ascending order: ' ', 'a', 'b', ..., 'z'.
Constraints
- text will contain between 1 and 50 characters, inclusive.
- prefix will contain between 1 and 50 characters, inclusive.
- suffix will contain between 1 and 50 characters, inclusive.
- text, prefix and suffix will contain only lowercase letters ('a'-'z') and spaces (' ').
Examples
"something"
"awesome"
"ingenious"
Returns: "something"
The example from the problem statement.
"havka"
"eto"
"papstvo"
Returns: "a"
The return value must be non-empty string, so the correct answer is "a".
"a"
"b"
"c"
Returns: "a"
The return value must be non empty string, so the correct answer is "a".
"abracadabra"
"habrahabr"
"bracket"
Returns: "abrac"
"mississippi"
"promise"
"piccolo"
Returns: "ippi"
"a a a a a a"
"a a"
"a"
Returns: "a a"
"z vt no k bdmztq ct lk ot e bref vr czff"
"tcrmy qrxw cl w"
"cj zi dp"
Returns: " bdmztq c"
" e mcytuzce u msgh fgi lw quyukw b"
" wapl yl s kq"
"abw rv"
Returns: "q"
"ogpu rjgq mtf z"
" k"
"gzk"
Returns: " rjg"
"n xfixx g j ouii tez uaqmehobr bh ltdw qu"
"z s mi nv xlc a"
"qif"
Returns: "aq"
" yvy iz hoc t awib p g"
" yl g"
" n s"
Returns: " g"
"x jv u tnj jfdh hz zhr emo nmv"
"gmu"
"m c"
Returns: "u tnj jfdh hz zhr em"
" a pc e cg h y g opyeijc t eonjwoh kdm q o"
"h"
"m rhnp nnzig qj"
Returns: "h kdm "
"e pnwd zwthplk l k ybkbv elbbcqi w cbv d wyz wab"
" ln irp qamkui g d ndwb"
"pj hci ef t v r j ulpdg p i j"
Returns: "b"
" xx crahded mitc aj i y k qiamjtls"
" ud kg"
"acp fte iaj"
Returns: " a"
"eu mdvv un z y laer fk vk f vx x xb g kwmu gg"
" e iua a"
"t kpwbd m"
Returns: "a"
"gn i"
"ro"
" h"
Returns: " "
"bwpoq hd jo q recw bg obmq k vr ct kkljcjx"
"u ljikxxhzc as"
"hyd p"
Returns: " h"
" xb yl qmof di ctqpq na icdrlgkq fjbej"
" n"
" lw"
Returns: " na "
"kqkoefah ys i jfhguzrd qm q k lra"
"qe kp mmr"
"m dfp bc y m vt"
Returns: "rd qm "
"tmuh rlbfqxdn t g atd zggby"
"gfv fb"
" mo un vpi v s"
Returns: "bfqxdn "
"zppowg qzreqw rjj qh pixa v"
"suc"
"zpa d t"
Returns: "zp"
"eq hc q t lnvw"
"x"
" ef ok t"
Returns: " "
" u wczb v"
"z"
"sox"
Returns: "z"
"bqevduspk jn jnw k u gv yf ax bjwwis ymh w knup"
"ghwdrovpwwbywm ryr"
"pp qqd"
Returns: " ax bjwwis ymh w knup"
" fed vvd gweac odk a lbderviy la q tyar r snr p"
"o yhg rgda"
"zv opmmcquup"
Returns: "a"
"kgs gjb klormak s cbx xvh im oaj o dt c n l"
"b j dojez foxyi"
" yto v z aibbe r pde g"
Returns: "im "
" xcq n l ldro k kgb n j xwkno ukc b l t r agmah b"
"p y he"
" bwokq hav"
Returns: " agmah b"
" cu ldp oyjy c tso rw b hkp pd"
" bm q ihn"
" ccxw"
Returns: " c"
" kcy"
" g"
"o x"
Returns: " "
"gpz t c vd u yqof"
"on fkz"
" n"
Returns: "z "
" xnt reje l uvi lzca tlbqelkjd wp kik"
"d zpg yvnota"
"o"
Returns: "a"
"fl wn dkf"
" vx m"
"d"
Returns: " d"
"jhxc le lizh zt"
"w"
"vvucg v"
Returns: " "
"qn okxyo"
" ybx p"
" d"
Returns: " "
"pcu r byga x g z k ab x hcn e qw th"
"ktukuq j q"
"pp gmi"
Returns: " q"
" dkx vo j"
"g"
"sqc"
Returns: " "
"r o tejmrmdpdyu daz zw jnattfbhpo"
"o gt p jcnapp"
" ksd f ww y"
Returns: "pdyu "
" d wbhxydy v twjpc aj c dazklu qt cexf ed"
" ycc i dgto vn"
" lgf zz q g"
Returns: " "
"ig lv msttp wk iuki ezwfnuxdq odg"
"wf lsi ua hbaa"
"epg mfvs ft lpwk x"
Returns: " e"
" k t zdr"
"m"
"c"
Returns: " "
" ght w xq g m g r"
" s w ue"
"tp"
Returns: " ght"
"q kbf pzyc tqlw ateaozmdprzkw s t v ieyofyn"
"dtmx w mehp e"
"gkkac"
Returns: "e"
"z s agzjztn iqo b qnu m d zb jd hi figsckyho q"
"f rfkw dxt hf q m"
"jrxwfis xt f padqx c hfl ut "
Returns: " m d zb j"
"x gv xdw vvj v hmlwsaz atftosucne fc ocf"
" pryxfkt v s m z wr k p jftz byc "
"s i arf wyleqmyou frxs lk"
Returns: "c "
" p lqq g ix ndc oix gnh lk qiw gafz mzqxqp vxw "
" qcsq mn"
"u"
Returns: "n"
"e stjlv s iis lphme io k jgvj ls p at"
"svfv a zic dlz sb gej "
" w x tpye "
Returns: "j "
" teysti ycqvy djqvu zpusk py iflwnmf zf cw e"
" l f m dbwr pr dtg"
" s y vt tjb e q w l upovs"
Returns: " "
"bg f mcc pgviscr vd d orom qje bnduuoc"
"qfof hyfkix xiyuxk p"
" s cca onl u"
Returns: " pgviscr "
"opgez sii rahs ny em xwy crboz zfmnkkoioe "
" lfwo bpww nd lfkaa ftvemdmdvc wom ie"
" sxiu ws d r j obbu xnsm nfs ond sa"
Returns: "ez s"
"ml ctqwd soaug dhwj zm u ewwo z ef"
"mdy tcxsvja s bsng zjqrpya ajsdy sl k c l "
"qciwpmeti hn j w tr hhisdi bhzq h "
Returns: "l ctq"
"lcxeux pambpclh gs i ik eg n lkmn aw yl"
"y dsg e uqtz th xvm wahe "
" r tmp hb j wrzb odhgon jniq ov zir"
Returns: " "
"ayo lth y f zhosk qphy gryyt og dmpnzm g we "
" j f y gx tezejhrx atizkmu x "
" ou wftloc n hcnkbzv slhv"
Returns: " f zhosk qphy gryyt o"
"mwdvp bu lu z gbnex h zqd njfe denxm yplj"
"frktdsdyqx gv w pey"
"slpxkqltc t ffhlbfcywtf"
Returns: "y"
"cz cu orlmjfksa jlqabom dh kqbtzbs qavdo k v "
"x hcb zho zn arg cuu udc mb"
" npo e pedhtbh uvw "
Returns: "bom "
" we sybh nr pxrrq m hob pqcenf ntjzypxo"
" e slkmbu mlpxsyai g efryp opl qw aa x"
"zrie qujljv nglukgam enhjq"
Returns: "xrrq m hob pqcenf ntjz"
"f fv hr jakiy qz o zxaismar p ergzmoovxojwg"
"xc g d ul r a o l ym urin lolg c csni "
"nq eyeb"
Returns: " "
" jkqcquk tfdrkbtffr t fk bctrcbkbjcvc r sm y mm"
" y mndmwvue t yptd f dij"
"n y slowf mtgew g lewkb "
Returns: "j"
"qythmoqh rq boftg ypex g og g p wis c dh r"
" frnjzkvuqv lw gi gy dftt isgmmwds aupdhi"
"ay w f y pu dcq kdu nyn "
Returns: "i"
"qp pesgwq ox ue n up xeuopw w ypawctwax qs g"
"z fym jh b uq rufmp heogc mwvxz zrnuci"
"cjszu soubczr"
Returns: " n up xeuopw w ypawc"
"kay msqblixtzxau qit omk xz kltfmevbdsvj ud"
"zsvl gpmk ionqrgjuirbss no xbos pfl"
"w"
Returns: "l"
"syvf yh g brfsj vxhgofk k ecey zknp ttp cjn tg "
"rn ofjic i dbtji a y szdqo"
" "
Returns: "ofk "
"qlmujs midzkpuon glikqm t t puxu c jspmbpujur"
"t zui ppw jyd "
"uof w k slkfkf sfbhsu vbz vsa kznq "
Returns: " midzkpuo"
"aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa"
"aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa"
"aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa"
Returns: "aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa"
" oriyty gln ghn zhpxyzqqn ar vxbln dg zmzzfcaf "
" d ox rds gwblg bcx qb vf czf kdgyliyy j esoy"
"bfbpi hhlxg obd g e ruqhq ie xy lxm t u ef "
Returns: "y gln ghn zhpxyzqqn ar vxb"
"ahdaqbfwyjc y x h qlkteom mf it krj juuvbsttva f"
" h ptnybkqd m wemklzn o fcf breg ie lyxlx w"
"b gs b t u af mw p zj jq iwdg ew t w h uh"
Returns: "wyjc y x h qlkteom mf it krj juuvb"
"wrr zzo qt hgm rpneh awte o pcjvaa rb axgu cx"
"yigx e wpujledx ohut a ey v de lkzt x juvl"
"h ke rjpskpidwbg zojhc rsdjsi hobbxglyr rp tgh a "
Returns: " zzo qt hgm rpneh "
"wrr zzo qt hgm rpneh awte o pcjvaa rb axgu cx"
" zzo qt hgm rpneh awte o pcjvaa rb axgu cx"
"wrr zzo qt hgm rpneh awte o pcjvaa rb axgu"
Returns: " zzo qt hgm rpneh awte o pcjvaa rb axgu cx"
"wrr zzo qt hgm rpneh awte o pcjvaa rb axgu cx"
"wrr zzo qt hgm rpneh awte o pcjvaa rb axgu"
" zzo qt hgm rpneh awte o pcjvaa rb axgu cx"
Returns: "wrr zzo qt hgm rpneh awte o pcjvaa rb axgu cx"
"ab"
"b"
"a"
Returns: "b"
"missidsgssippi"
"proddmise"
"piddccolo"
Returns: "dsgssippi"
"bcd"
"efg"
"hjk"
Returns: "b"
"b"
"x"
"y"
Returns: "b"
"abababbab"
"ababababaab"
"abaababab"
Returns: "aba"
"aaaa aaaaaa"
" qqqqqqqqqq"
" ssss s"
Returns: " "
"iiiiii"
"a"
"b"
Returns: "i"
"tttt"
"aaa"
"bbb"
Returns: "t"
"bbbb"
"aaaa"
"ccccc"
Returns: "b"
" "
"a"
"b"
Returns: " "
"r"
"x"
"b"
Returns: "r"
"bc"
"d"
"e"
Returns: "b"
"zz"
"a"
"a"
Returns: "z"
"b"
"a"
"a"
Returns: "b"
"bacabadabacabaeabacabadabacaba"
"abacabada"
"bacac"
Returns: "abacabadabaca"
"az"
"b"
"c"
Returns: "a"
"abc"
"e"
"f"
Returns: "a"
"abcdefghijklmnopq r s t uvwx"
"abcdefg r s jldf fjd"
"uvwxyz"
Returns: "defghijklmnopq r s t uvwx"
"bxxxxxefgcdxxxxabxxxxcd"
"ttab"
"efgcdtt"
Returns: "bxxxxxefgcd"
"cabacbaddadaaddbabccaddaddbdacadbabddbbcdacdcbc"
"dbddaddaaadacadabdaadbbcaadddaaaabcbdabadaabcdcdb"
"dbddaddaaadacadabdaadbbcaadddaaaabcbdabadaabcdcdb"
Returns: "dbabccaddaddbd"
"hzvkz"
"eto"
"papstvo"
Returns: "h"
"abcd"
"abc"
"bcd"
Returns: "abcd"
"abdbaabcba"
"ab"
"ba"
Returns: "abcba"
"aafdasdfasdaasfdasdffdasdfasdaafdasdfasd"
"afasdfatrhertghsfsdhsdfaassaafdasdfasddfasdfasdf"
"aasdfasdfaafdasdasfasdfasfdasfdyrefasdaafdasdfasda"
Returns: "asdfasdaas"
"aaaaa"
"f"
"aaaa"
Returns: "aaaa"
"z"
"x"
"y"
Returns: "z"
"b"
"c"
"d"
Returns: "b"
"bcd"
"x"
"z"
Returns: "b"
"xxxeabxxxfeaxxx"
"dfe"
"abc"
Returns: "fea"
"axxxxxxxtyyyaxxxxkkktyyy"
"llla"
"tlll"
Returns: "axxxxkkkt"
"ab"
"fgg"
"ghhh"
Returns: "a"
"aba"
"xxx"
"aba"
Returns: "aba"
"bb"
"a"
"c"
Returns: "b"
"bcd"
"gf"
"ij"
Returns: "b"
"chetan"
"he"
"ta"
Returns: "heta"
"havak"
"eto"
"papstvo"
Returns: "a"
"zbcdefghjik"
"q"
"zbcdefghjik"
Returns: "zbcdefghjik"
"ab"
"x"
"y"
Returns: "a"
"x"
"a"
"b"
Returns: "x"
"zz"
"ab"
"ba"
Returns: "z"
"abcdftab"
"tab"
"c"
Returns: "tab"
"dfd"
"a"
"a"
Returns: "d"