[HackerRank]情書的秘密(The Love-Letter Mystery)

題目描述

詹姆斯找到了一個他朋友亨利寫給他女朋友的情書。詹姆斯想要惡搞一下,所以他決定更改這封情書的內容。他把情書裡所有的字都變成回文。他可以將字串的字元值減少,例如「d」可以變成「c」,但「c」不能變成「d」,每減少一個字元值就算是一次操作,當字元是「a」時就不能再減少了。為了讓每組字串都變成回文的格式,他必須重複多次這個動作。請找出將每組字串改成回文的最小的操作次數。

原題網址

https://www.hackerrank.com/challenges/the-love-letter-mystery

輸入格式

第一行為一個整數T,表示接下來要輸入的字串數量,範圍在1到10之間(包含1和10)。接下來的T行,每行都是一組字串,字串長度範圍在1到10000之間(包含1和10000),字串的字元都是小寫英文字母

輸出格式

分行輸出每組輸入的字串要改成回文的最小操作次數。

範例輸入

4
abc
abcba
abcd
cba

範例輸出

2
0
4
2

額外解釋

第一組字串的變化過程:abc -> abb -> aba,共操作了兩次。
第二組字串的變化過程:abcbaa,原本就是回文。
第三組字串的變化過程:abcd -> abcc -> abcb -> abca -> abba,共操作了四次。
第四組字串的變化過程:cba -> bba -> aba,共操作了兩次。

解題概念

這題看起來有點複雜,其實只要將字串的中間當作鏡射的基準,從最外一直向中央靠近計算中央兩端字元值之差的絕對值總和,即為題目所要的「操作次數」。

參考答案

關於作者

Magic Len

Magic Len

各位好,我是Magic Len,是這網站的管理員。我是台灣台中大肚山上人,畢業於台中高工資訊科和台灣科技大學資訊工程系,曾在桃機航警局服役。我熱愛自然也熱愛科學,喜歡和別人分享自己的知識與經驗。如果你有興趣認識我,可以加我的Facebook,並且請註明是從MagicLen來的。

相關文章