切換
舊版
前往
大廳
主題

ZeroJudge - e524: 106 彰雲嘉區複賽 - Q4 變位字判斷 解題心得

Not In My Back Yard | 2020-07-30 00:18:12 | 巴幣 0 | 人氣 182

題目連結:


題目大意:
輸入第一列給定一正整數 n ,代表有 n 筆測試資料,每筆佔兩列。測資的兩列都會各自給定一字串(可能含有空白字元),請判斷兩字串是否互為易位構詞(即 Anagram,並且此題忽略大小寫的差異同時也忽略英文字母以外的字元)。如果是,輸出「1」;反之,輸出「0」。



範例輸入:
2
Abcba-Daba Kbbcaa!
Caba. Bad, Bakaacbb.
Abc, Ddeff-Gh!
Bdd. Cae. Fgh.


範例輸出:
1
0


解題思維:
建一個大小 128 的陣列,用以計算字元的出現次數(初始值當然都是 0)。

接著掃過第一個字串,然後將每個碰到的字元依照 ASCII 編碼對應到的位置之儲存的出現次數 + 1 (即代表該字元出現次數 + 1)。

接著掃過第二個字串。類似於第一個字串,但是每個出現的字元,其出現次數 - 1。

以上當中將所有的大寫字母都轉成小寫,小寫則不變(反過來也行),其他字元忽略。

最後看字母 a ~ z (或是 A ~ Z)的出現次數是否皆為 0 。如果是,則代表兩者是易位構詞,則輸出「1」;反之,代表不是易位構詞,輸出「0」。




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

創作回應

更多創作