[HackerRank]變位詞(Anagram)

題目描述

錫德對於閱讀短篇故事很著迷,作為一個電腦科學的學生,他想對這些書做一些分析。他選擇了S1和S2兩個字串,這兩個字串的長度差距小於等於1。你的任務是要找出至少需要更改多少字串S1的字元,才使它跟字串S2是變位詞(Anagram)的關係。

原題網址

https://www.hackerrank.com/challenges/anagram

輸入格式

第一行為一個整數T,表示有幾組測試資料,範圍在1到100之間(包含1和100)。接下來的T行,每行都是一組測試字串,這個字串是字串S1和字串S2串接起來的結果,長度在1到1000之間0(包含1和10000),由小寫英文字母組成。

輸出格式

分行輸出每組輸入字串測試的結果。也就是需要更改多少字串S1的字元,才使它跟字串S2是變位詞(Anagram)的關係。

範例輸入

6
aaabbb
ab
abc
mnop
xyyx
xaxbbbxx

範例輸出

3
1
-1
2
0
1

額外解釋

第一組測試中,字串S1為「aaa」,字串S2為「bbb」,所以需要將字串S1改成「bbb」才能跟字串S2是變位詞的關係,共改變了3個字元。

第二組測試中,字串S1為「a」,字串S2為「b」,所以需要將字串S1改成「b」才能跟字串S2是變位詞的關係,共改變了1個字元。

第三組測試中,「abc」的長度是單數,沒辦法切成長度一樣的字串S1和字串S2,它們不可能是變位詞的關係。所以輸出「-1」。

第四組測試中,字串S1為「mn」,字串S2為「op」,所以需要將字串S1改成「op」或是「po」才能跟字串S2是變位詞的關係,共改變了2個字元。

第五組測試中,字串S1為「xy」,字串S2為「yz」,已經是變位詞的關係,不用改變任何字元。

第六組測試中,字串S1為「xaxb」,字串S2為「bbxx」,所以需要至少將字串S1的「a」改成「b」才能跟字串S2是變位詞的關係,共改變了1個字元。

解題概念

所謂的「變位詞(Anagram)」是指由相同數量的字母所排列組合而成的字串,例如「now」和「won」就是變位詞的關係。

在這題由於輸入的測試字串是字串S1和字串S2串接後結果,但由於變位詞的字串長度要相等,因此如果測試字串的長度是單數的話,可以立即知道不管字串S1和字串S2是怎麼切割的,它們一定不是變位詞的關係,直接輸出「-1」即可。

測試字串的前半段為字串S1,剩餘的後半段為字串S2,利用「HashMap」分別記錄它們所包含的字元以及數量。由於是要更改字串S1的字元,所以之後要去找出字串S2擁有的字元,在字串S1中要加多少數量才會跟字串S2中的一樣,把這個數量累加之後就是字串S1至少需要改變的字元數量。

參考答案

關於作者

Magic Len

Magic Len

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

相關文章