切換
舊版
前往
大廳
主題

ZeroJudge - a872: 12. Abbreviation Expansion 解題心得

Not In My Back Yard | 2019-08-25 23:28:33 | 巴幣 0 | 人氣 198

題目連結:


題目大意:
給定兩部分的輸入,第一部分代表字典,有好幾個以空白互相分隔的單字(大小寫英文字);第二部分是一個文字經過簡寫的文章(大小寫字母加標點符號)。兩部分以一個「|」作為分隔。

請將簡寫的文章還原成原始的文章。還原方式為:每一個簡寫的單字,在字典中找出需要增加最少的字母便可組成的單字,就是原始的本文;若有兩個(含)以上符合的單字,則輸出簡寫的單字本身。



範例輸入:
cream chocolate every ever does do ice is fried friend friends lick
like floor favor flavor flower best but probably poorly say says that
what white our you your strawberry storyboard the | wht flvr ic crm ds
yr bst fnd lke? ur frds lk stbry, bt choc s prly th bs flr vr!


範例輸出:
what flavor ice cream does
your best friend like? our friends lk strawberry, but chocolate is poorly the best floor ever!


解題思維:
不困難但是稍微麻煩一點的題目(因為原題的資訊量超級少,題目大意都還比原題資訊多)。

總之,用一個字串陣列將「|」前的單字全數儲存起來。接著,對於每個「|」後的字串 s (彼此以空白隔開的單字們)去字串陣列裡找有哪些單字有含 s 中的所有字母。

找出那些單字後,與每個單字的長度減去 s 的長度即為需要補齊的字母數。然後,找出需要最少的那個單字,即是所求;如果有多個或是根本就沒有符合的單字,就輸出原本的字串 s 。

接著是簡寫的文章中較麻煩的點:標點符號。需要特別將標點符號兩側的字串隔開,然後去作上面的檢查,看要輸出什麼文字。最後兩邊的文字中間的空格以原本的標點符號替代。

此次分享到此為止,如有任何更加簡潔的想法或是有說明不清楚之地方,也煩請各位大大撥冗討論。

創作回應

相關創作

更多創作