bloggoHyphenate

SRM 214 · 2004-10-06 · by Eeyore

SRM 214 · 2004-10-06 · by Eeyore · Search, String Manipulation

Show categories

Class Name: bloggoHyphenate

Return Type: String[]

Method Name: correct

Arg Types: (vector<string>, vector<string>)

Problem Statement

Bloggo is a system for managing weblog content. It offers a number of natural-language editing services, among which is a hyphenation checker. Hyphenation is the insertion of a hyphen character, '-', between two syllables of a word. Although it is possible to use an automatic hyphenation algorithm to achieve uniform line length, some users prefer to hyphenate manually. These users can set the hyphenation checker to lazy mode, which restricts it to verifying words that already contain a hyphen.

Your fellow bloggo developers have already written code that identifies hyphenated words in a user's file. Your job is to verify these words and correct them as necessary. As a guide to proper hyphenation, you are given a String[] named dictionary, each element of which contains a word separated into its syllables by single spaces. For example, the syllabization of the words "syllable", "hyphenate", and "antidisestablishmentarianism" would be represented as follows.


  syl la ble

  hy phen ate

  an ti dis es tab lish men tar i an ism

You are given another String[], candidates, each element of which contains a word drawn from dictionary, but without the spaces and with the addition of a single hyphen. If the hyphen is correctly positioned between two syllables of the word, this is to be signaled with the result String "correct". Otherwise, move the hyphen from its erroneous position to the nearest correct position. In the event of a tie, choose the position nearer to the left. If the word is actually monosyllabic, remove the hyphen altogether. Return a String[] containing, for each element of candidates, the corresponding result String.

Constraints

dictionary contains between 1 and 50 elements, inclusive
each element of dictionary is between 1 and 50 characters long, inclusive
in each element of dictionary, neither the first nor the last character may be a space
in each element of dictionary, there may not be two consecutive spaces
the only characters allowed in dictionary are the space character and the lowercase letters 'a' to 'z'
each element of dictionary is unique after removal of spaces
candidates contains between 1 and 50 elements, inclusive
each element of candidates is between 1 and 50 characters long, inclusive
each element of candidates contains exactly one hyphen
for each element of candidates, if the hyphen were removed, it would match an element of dictionary after removal of spaces

Examples

{"syl la ble", "dic tion a ry", "mole"}
{"mo-le", "syl-lable", "syll-able", "dictio-nary", "dictionary-",
 "-syllable"}
Returns: { "mole",  "correct",  "syl-lable",  "diction-ary",  "dictiona-ry",  "syl-lable" }

{"ajx zox u", "jox xefr yu tsv xdf gyx", "jt kfcg rbqn q", "d zcz xv ix", "rtdm afdv hx ix lf ufr", "x hwt p gmef pzow qfzf", "hu mhrf st", "h sksc", "pfv np s rnp", "vloq f v bz gza betd", "omq yh ieam i aaev m ay", "pbwv fw eqj zux zbhn jo", "p x zwvj", "k qq v u zuw go mowx", "bro o tfx gdov", "zf j l vbi oxme s qo kl os", "ba e cw o zr sh t", "xj uyyp vg x hp msen", "kw xz zbw wewo sr", "dd nt gum toq cnf mncp qh sv", "cl zyxh o wot aa jt ktp gz", "kznt d qw", "g m zu znj uxv wm li", "geh i cw ejjr", "ixpn gdi x uwbu zh xi", "dqj oju", "t g qkdi d svyn kk e", "fx qt r rhmv", "r an itw qd avs g wpid", "loo tvp", "vvf g ds i jlos cy ps rx", "ubg vzmo n ov qktu", "q wwt r j w gbhl", "q rd eshz dp ingh yqse", "gn plf vx jll mxar od fzmh on dqvl", "i smtl v azm jf s", "lv qro", "g yjnp lgy plf biv gpwj wvg b tm sq", "eve lkc", "sff ub", "a fi peo pzzd lib", "m tho ic hdip ju py", "z jgu myx ffr", "eb ai gf vwwh umz kkxh", "vwy skpz lgkx rbll", "n v npul", "z om pe gn p", "mf vq edrb", "leun irnf agz hmd v", "ysx ix d kodi sk"}
{"-evelkc", "-hsksc", "-ismtlvazmjfs", "afipeo-pzzdlib", "ajxzox-u", "b-rootfxgdov", "baecwozr-sht", "clzyxho-wotaajtktpgz", "ddntgumtoqcnfmncpqh-sv", "dqjoj-u", "dzcz-xvix", "ebaigfvww-humzkkxh", "fxqtr-rhmv", "gehic-wejjr", "gmzuznjuxvwml-i", "gnplfvxjllmxarodfz-mhondqvl", "gyjnplgyplfbivgpwjwvgbtmsq-", "humhrfst-", "ixpngdixu-wbuzhxi", "joxxefr-yutsvxdfgyx", "jtkf-cgrbqnq", "kqq-vuzuwgomowx", "kwxzzbw-wewosr", "kzn-tdqw", "leunirnfa-gzhmdv", "loo-tvp", "lvq-ro", "mfv-qedrb", "mthoic-hdipjupy", "nvnpu-l", "omqyhi-eamiaaevmay", "pbwvfweqjzux-zbhnjo", "pfvn-psrnp", "px-zwvj", "qrdeshzdpingh-yqse", "qwwtrjwgbhl-", "ranitwqdavsgwp-id", "rtdmafd-vhxixlfufr", "sf-fub", "tgqkdid-svynkke", "ubgv-zmonovqktu", "vloqf-vbzgzabetd", "vvfgdsijl-oscypsrx", "vwyskpzlgkxrbl-l", "xhwt-pgmefpzowqfzf", "xjuyypv-gxhpmsen", "ysxix-dkodisk", "zfjlvbioxmesqok-los", "zjgumyxffr-", "zompegn-p"}
Returns: { "eve-lkc",  "h-sksc",  "i-smtlvazmjfs",  "correct",  "correct",  "bro-otfxgdov",  "correct",  "correct",  "correct",  "dqj-oju",  "correct",  "ebaigfvwwh-umzkkxh",  "correct",  "gehi-cwejjr",  "gmzuznjuxvwm-li",  "gnplfvxjllmxarod-fzmhondqvl",  "gyjnplgyplfbivgpwjwvgbtm-sq",  "humhrf-st",  "ixpngdix-uwbuzhxi",  "correct",  "jt-kfcgrbqnq",  "correct",  "correct",  "kznt-dqw",  "leunirnf-agzhmdv",  "correct",  "lv-qro",  "mf-vqedrb",  "correct",  "nv-npul",  "omqyh-ieamiaaevmay",  "correct",  "pfv-npsrnp",  "correct",  "correct",  "qwwtrjw-gbhl",  "ranitwqdavsg-wpid",  "rtdmafdv-hxixlfufr",  "sff-ub",  "correct",  "ubg-vzmonovqktu",  "correct",  "vvfgdsi-jloscypsrx",  "vwyskpzlgkx-rbll",  "correct",  "xjuyyp-vgxhpmsen",  "correct",  "zfjlvbioxmesqo-klos",  "zjgumyx-ffr",  "correct" }

{"d jug x jg", "jcpe ix cmad frzf pjv sn ccf", "b daop h fngf y ec", "r nqi np cd a i kn h xhcv", "bvqd zbx btm lzt lfz", "arlx lb l ddk f", "z y kpvi myy ggw", "cxhw u qmbb iy xfsu", "cl rhar", "zkxz", "es wfgg fkro rdmb", "htd gcm ervf", "y y u yho dgt mut jzbr", "lvxt sxbe flj kwe u tr ouze kgom", "u fvgt r", "ebmc nnz jgcn fqa xvdb", "ad zq abjz lgp lv", "qzu ml oul kntr txmb qetg tzy", "xkp pu jtd ph xawa", "gucp cy", "m nz wsyg jac", "ispw ecu xmp thk", "wkds re th cso oil xz arwx qra zrdf", "di dm rk bqd", "xsh cqh wqdk lfoq", "b cw sd wkh hpna", "ci lon km", "djs xd ab jy lw vos d tcw", "dozx f mzy xd ana vq", "x dq x m nn", "zss mrpg ewdt fdvw p c mda", "zp rpg ph ksnk", "txts a eqtv u va", "fkn n yfuq ubuo qe he", "eo uqo ob ntlj y d uoqn dvsi u", "cp umr no kdy c", "pt g rkxw dtx gm fixl", "rvnc v dim", "wgk abp ihn xm", "b c xmwa knk kj ymku", "tvam vdpf o qn q qkoj f", "cw n ur glg g bny", "maiy uxvj um ameb hhzu", "r vkxm gfto usx txw huq ypoe", "vuhk hflt gjn", "n nsh wfxt sw bnyj", "g c nw bjsp dk d", "qd gfi z zst kq r", "x p kr gkhx", "v rm mq fe"}
{"-bcwsdwkhhpna", "-djugxjg", "-htdgcmervf", "-vrmmqfe", "-vuhkhfltgjn", "-wgkabpihnxm", "-wkdsrethcsooilxzarwxqrazrdf", "-xdqxmnn", "adzqabjz-lgplv", "arlxlblddk-f", "bc-xmwaknkkjymku", "bdaophfn-gfyec", "bvq-dzbxbtmlztlfz", "c-ilonkm", "c-wnurglggbny", "cl-rhar", "cpu-mrnokdyc", "cxhwuqmbbiyxfsu-", "di-dmrkbqd", "djsxdab-jylwvosdtcw", "do-zxfmzyxdanavq", "ebmcnnzjgc-nfqaxvdb", "eouqoobn-tljyduoqndvsiu", "eswfggfkror-dmb", "fknnyfuqub-uoqehe", "gcnwbj-spdkd", "gucp-cy", "ispwe-cuxmpthk", "jcpeixcmadfrz-fpjvsnccf", "lvxtsxbefljkweut-rouzekgom", "maiyuxvjumamebhhz-u", "mnzwsygja-c", "nnshwfxtswbny-j", "ptgrkxwdtxgmfix-l", "qdgfiz-zstkqr", "qzumloulkntrtx-mbqetgtzy", "rnqin-pcdaiknhxhcv", "rv-ncvdim", "rvkxmgftousxtxwhuqyp-oe", "tvamv-dpfoqnqqkojf", "txtsa-eqtvuva", "ufvgt-r", "xkpp-ujtdphxawa", "xp-krgkhx", "xshcqhwqdklfo-q", "yyuyho-dgtmutjzbr", "zkxz-", "zprpgphk-snk", "zssmrpgewdtfdvwpcmd-a", "zykpv-imyyggw"}
Returns: { "b-cwsdwkhhpna",  "d-jugxjg",  "htd-gcmervf",  "v-rmmqfe",  "vuhk-hfltgjn",  "wgk-abpihnxm",  "wkds-rethcsooilxzarwxqrazrdf",  "x-dqxmnn",  "correct",  "correct",  "correct",  "bdaoph-fngfyec",  "bvqd-zbxbtmlztlfz",  "ci-lonkm",  "cw-nurglggbny",  "correct",  "cp-umrnokdyc",  "cxhwuqmbbiy-xfsu",  "correct",  "correct",  "dozx-fmzyxdanavq",  "ebmcnnzjgcn-fqaxvdb",  "eouqoob-ntljyduoqndvsiu",  "eswfggfkro-rdmb",  "fknnyfuq-ubuoqehe",  "gcnw-bjspdkd",  "correct",  "ispw-ecuxmpthk",  "jcpeixcmadfrzf-pjvsnccf",  "lvxtsxbefljkweu-trouzekgom",  "maiyuxvjumameb-hhzu",  "mnzwsyg-jac",  "nnshwfxtsw-bnyj",  "ptgrkxwdtxgm-fixl",  "correct",  "qzumloulkntr-txmbqetgtzy",  "rnqi-npcdaiknhxhcv",  "rvnc-vdim",  "rvkxmgftousxtxwhuq-ypoe",  "tvam-vdpfoqnqqkojf",  "correct",  "correct",  "xkp-pujtdphxawa",  "correct",  "xshcqhwqdk-lfoq",  "correct",  "zkxz",  "zprpgph-ksnk",  "zssmrpgewdtfdvwpc-mda",  "zykpvi-myyggw" }

{"grt v r egr xqt p kh", "i prv ews w bccr gpl cgk", "lcid g i e bjpt chyo e nsb adih", "jxgl echq fv luj es", "zqj uqig zsu vdxq euj xr", "iren sru", "lv h v zn qwjb d", "occy vail oga", "csi nyu igfj ucb h", "goq p rv s", "epu qlef t u tk s", "h edu mn fe", "w i hvjg o o qk ga buc edh", "arwr gtbt qnd ei ue dtcz ctol x", "jczd ydf y", "u dzc ny d ww nwd ywas oob", "d igo", "gh c crr vnel ahku snnl dk", "d uvkd j z i i", "cqh gem z r qx hgv", "die wdyu", "q kks p", "meo ep az ujar kbmj bkqb ddu basn", "oq if rm mod ytep", "vwt x voc sls", "ncrv ndjr nk qsb cjp li zqx", "fc bpbp ugo taxt k", "ke woj y x l flhw", "zz ed qc gxve", "uu xu", "ul qw izm lkv", "k edb dcnn vlf be er", "mb rda gws pn mnut", "znjj o w it ycaz pb xjvr", "szy zu qh ohaj yuk vl vzo", "coz w h b zosy t", "pv qohg pwkp m r egrz", "n sv zjh ib het x", "im xnc apgi gzax hjl wq cx yhqc", "m h sql gpnq kyu x", "zpw e cdd vn j", "uenz jb xkv", "nluh aci jz usld iwk hss ix zv", "o sh xq yt sss", "apge mozp rzsi ioaf ckwn", "rwm kuow xjq yev e", "j rgic swmo sogq", "kyha zfo mo x wctl vff", "tjve sz bws a kaz", "keas lpy vug ngk ke qt"}
{"-kedbdcnnvlfbeer", "-qkksp", "apgemozprzsii-oafckwn", "arwr-gtbtqndeiuedtczctolx", "cozwh-bzosyt", "cqhgemzrqxhg-v", "csinyuig-fjucbh", "diew-dyu", "digo-", "duvkdjzi-i", "epuql-eftutks", "fcbp-bpugotaxtk", "gh-ccrrvnelahkusnnldk", "goqprv-s", "grtvregrxqtpkh-", "he-dumnfe", "imxncapgigzaxhjlwqc-xyhqc", "iprvewswbccrgp-lcgk", "irensr-u", "j-xglechqfvlujes", "jczdy-dfy", "jrgi-cswmosogq", "k-ewojyxlflhw", "keaslpyvugngkke-qt", "kyh-azfomoxwctlvff", "lc-idgiebjptchyoensbadih", "lv-hvznqwjbd", "mbrdag-wspnmnut", "meoepa-zujarkbmjbkqbddubasn", "mhsq-lgpnqkyux", "ncrvndjrnkqsbcjplizqx-", "nluhacijzusld-iwkhssixzv", "nsvzj-hibhetx", "occyvailoga-", "oqifrmmodyte-p", "osh-xqytsss", "pvqohgpwk-pmregrz", "rwmkuowxjqyev-e", "szyzuqhoha-jyukvlvzo", "tjvesz-bwsakaz", "u-enzjbxkv", "udzcnydwwnwdyw-asoob", "ulqwizmlkv-", "uu-xu", "vwt-xvocsls", "w-ihvjgooqkgabucedh", "znjjow-itycazpbxjvr", "zpwec-ddvnj", "zqjuq-igzsuvdxqeujxr", "zzed-qcgxve"}
Returns: { "k-edbdcnnvlfbeer",  "q-kksp",  "apgemozprzsi-ioafckwn",  "correct",  "correct",  "cqhgemzrqx-hgv",  "csinyu-igfjucbh",  "die-wdyu",  "d-igo",  "correct",  "epu-qleftutks",  "fc-bpbpugotaxtk",  "correct",  "correct",  "grtvregrxqtp-kh",  "h-edumnfe",  "imxncapgigzaxhjlwq-cxyhqc",  "iprvewswbccrgpl-cgk",  "iren-sru",  "jxgl-echqfvlujes",  "jczd-ydfy",  "jrgic-swmosogq",  "ke-wojyxlflhw",  "correct",  "kyha-zfomoxwctlvff",  "lcid-giebjptchyoensbadih",  "correct",  "mbrda-gwspnmnut",  "meoep-azujarkbmjbkqbddubasn",  "mhsql-gpnqkyux",  "ncrvndjrnkqsbcjpli-zqx",  "correct",  "nsvzjh-ibhetx",  "occyvail-oga",  "oqifrmmod-ytep",  "correct",  "pvqohgpwkp-mregrz",  "correct",  "szyzuqhohaj-yukvlvzo",  "correct",  "uenz-jbxkv",  "udzcnydwwnwd-ywasoob",  "ulqwizm-lkv",  "correct",  "correct",  "correct",  "correct",  "zpwe-cddvnj",  "zqj-uqigzsuvdxqeujxr",  "correct" }

{"aag ilca p uort qqt uih imk", "xd pzlv iuda z", "zpj kqv v w ni qq", "yl dfsp", "ws mf p jau evzh wdzo jbcw", "x sjo", "sh jsjr vn", "ais ne u kyj sqt", "a kpde twph hf sz hvh eaeu", "cqyu ld tsm et", "myud ckj hk pv", "gfl fvex nw qk xpm usc bi", "iqbe v xrf xjt pd", "s i yzo q fvi bv jqby nrky m f nkyu", "x pued lln k du qnp qpgz kx", "lsl shg l c aqqq q", "tico jrd bt", "ebjn bs kjt d", "e rl ra huom", "sw sb rl qh i aomk", "spa uuue ldv gri uuyx pun", "wrlr dbh zj xsjt s tm zmk wdgs", "uflr f wsa jv irae", "clyp zhru", "so lu ffbe txz zhjs", "as g xqf xr wp ego v wskc", "x w b mln", "nxhy ekn s vw", "pj so uf ok", "vf rabw qfkp rs tofj", "te od jvzt kpyr fuev ynpo", "zlzw vfs da gwf", "idhr kqp yqo", "kehb auci b gl", "pb rtpv bw foib yklg aku vc gil", "mh s u izrf osy", "pztv r gd w jy r", "bxm m x n t khia hea bhd b", "mkh yain rkh ah gsam", "eshz r tea s hx", "f r bow y qusf lvlz", "mm vuc h jofc wyo", "ubt rf jptr", "dsrw c jj ry w ygar uf", "f jg", "g qq djq hiye udt acyx b sfje", "m m j iaww tboi u quc fzv", "thm kk keaf k we", "xbp mwm g dh be dr z v", "aro ajy q mhnx"}
{"-akpdetwphhfszhvheaeu", "-erlrahuom", "-mkhyainrkhahgsam", "-siyzoqfvibvjqbynrkymfnkyu", "-ticojrdbt", "-uflrfwsajvirae", "aagilcapuortqqt-uihimk", "aisneuky-jsqt", "aroajyqmhn-x", "asgxqf-xrwpegovwskc", "bx-mmxntkhiaheabhdb", "clypzhru-", "cqyuldtsm-et", "dsrwcjjrywy-garuf", "eb-jnbskjtd", "eshzrteas-hx", "fj-g", "frbowyqusfl-vlz", "g-qqdjqhiyeudtacyxbsfje", "gfl-fvexnwqkxpmuscbi", "id-hrkqpyqo", "iqbevxrfx-jtpd", "kehbaucibg-l", "lslshglcaqqqq-", "mhsuizrfos-y", "mmjiawwtboiuqucfz-v", "mmvuchjofc-wyo", "myudckj-hkpv", "nxhyekn-svw", "pbrtpvbwfo-ibyklgakuvcgil", "pjsoufok-", "pzt-vrgdwjyr", "shjsjrvn-", "soluffbetxzz-hjs", "spa-uuueldvgriuuyxpun", "swsbrlqhi-aomk", "teodjvztkpyrfuevynp-o", "thmkkkeafkwe-", "ubtrfjptr-", "vf-rabwqfkprstofj", "wrlrdbhzjxsjtstmzmkwdg-s", "wsmfpjau-evzhwdzojbcw", "xbpmwmgdhbedr-zv", "xdp-zlviudaz", "xpuedllnkduqnpqpgzkx-", "xsjo-", "xwbml-n", "y-ldfsp", "zlzwvfsd-agwf", "zpjkqvvwni-qq"}
Returns: { "a-kpdetwphhfszhvheaeu",  "e-rlrahuom",  "mkh-yainrkhahgsam",  "s-iyzoqfvibvjqbynrkymfnkyu",  "tico-jrdbt",  "uflr-fwsajvirae",  "correct",  "aisneukyj-sqt",  "aroajyq-mhnx",  "correct",  "bxm-mxntkhiaheabhdb",  "clyp-zhru",  "correct",  "dsrwcjjryw-ygaruf",  "ebjn-bskjtd",  "correct",  "f-jg",  "frbowyqusf-lvlz",  "correct",  "correct",  "idhr-kqpyqo",  "iqbevxrf-xjtpd",  "kehbaucib-gl",  "lslshglcaqqq-q",  "mhsuizrf-osy",  "mmjiawwtboiuquc-fzv",  "correct",  "correct",  "correct",  "pbrtpvbw-foibyklgakuvcgil",  "pjsouf-ok",  "pztv-rgdwjyr",  "shjsjr-vn",  "soluffbetxz-zhjs",  "correct",  "correct",  "teodjvztkpyrfuev-ynpo",  "thmkkkeafk-we",  "ubtrf-jptr",  "correct",  "wrlrdbhzjxsjtstmzmk-wdgs",  "correct",  "correct",  "xd-pzlviudaz",  "xpuedllnkduqnpqpgz-kx",  "x-sjo",  "xwb-mln",  "yl-dfsp",  "zlzwvfs-dagwf",  "correct" }

46)

{"syl la ble", "dic tion a ry", "mole"}
{"mo-le", "syl-lable"}
Returns: { "mole",  "correct" }

The word "mole" is monosyllabic, so we remove the hyphen. The word "syllable" is correctly hyphenated.

47)

{"syl la ble", "dic tion a ry", "mole"}
{"dictio-nary", "syll-able"}
Returns: { "diction-ary",  "syl-lable" }

We correct "dictio-nary" by moving the hyphen one position to the right. The hyphen in "syll-able" could be moved one position to the left or to the right, but we prefer the left.

48)

{"syl la ble", "dic tion a ry", "mole"}
{"dictionary-", "-syllable"}
Returns: { "dictiona-ry",  "syl-lable" }

Poorly placed hyphens indeed.

Submissions are judged against all 57 archived test cases, of which 8 are shown here. Case numbers match the judge’s.

Coding Area

Language: C++17 · define a public class bloggoHyphenate with a public method vector<string> correct(vector<string> dictionary, vector<string> candidates) · 57 test cases · 2 s / 256 MB per case