主題

ZeroJudge - a224: 明明愛明明 解題心得

Not In My Back Yard | 2021-04-19 00:00:01 | 巴幣 0 | 人氣 27

題目連結:


題目大意:
輸入有多列,每列給定一字串(由大小寫英文字母、標點符號組成,保證沒有空白字元、總長不超過 1000 個字元),試問該字串忽略掉非英文字母之符號後是否可以重組成一個迴文(忽略大小寫之差異)?



範例輸入:
ababa
bbaaa
Level
aaabbbcc
abcdefg
HowAreYouToday
A_man,_a_plan,_a_canal:_Panama.


範例輸出:
yes !
yes !
yes !
no...
no...
no...
yes !


解題思維:
類似這題,不過本題需要使用所有字母。而且大小寫的差異要忽略掉,例如 'A' 跟 'a' 視為一樣。

因此我們使用一陣列統計每種字元的出現次數,然後將大小寫的次數合併。

然後看有多少英文字母的出現次數為奇數(假設有 C 個)。因為一個迴文最多只能有一個出現奇數次的字母(也就是奇數長度迴文的中心),所以當 C ≦ 1 時,代表我們能將原字串重組成迴文;反之當 C > 1 時,代表我們無法將字串變成迴文。




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

創作回應

更多創作