題目連結:
題目意譯:
你被給定一個索引值從 0 開始的字串 word,其由小寫英文字母所組成。你需要選擇其中一個索引值並從 word 中移除位於該索引值的字母使得出現在 word 中的每種字母之頻率彼此一致。
如果可以藉由移除一個字母使得 word 中所有字母的頻率一致,則回傳真(True);反之,則回傳假(False)。
注:
一種字母 x 的頻率為其出現在一字串中的次數。
你必須移除恰好一個字母,不能選擇不做任何事。
限制:
2 ≦ word.length ≦ 100
word 只由小寫英文字母組成。
範例測資:
範例 1:
輸入: word = "abcc"
輸出: true
解釋: 選擇索引值 3 並刪除:word 變成了 "abc" 而每種字母的頻率皆為 1。
範例 2:
輸入: word = "aazz"
輸出: false
解釋: 我們必須刪除一個字元,所以要嘛會變成 "a" 的頻率是 1,而 "z" 的頻率是 2;要嘛兩者交換。不可能讓所有字母有著相同的頻率值。
解題思維:
其實是單純的邏輯題目。
假設我們已經統計完 word 中所有種類的字母之出現情況,並假設出現的最少次數為 x、最多次數為 y。則可以看到:
如果當 y == 1,則刪掉任何一個字母都可以符合要求。因為被刪掉的字母會變成出現次數為 0,而 0 次不會被條件的考慮範圍內。因此回傳真;
如果 x == y,且有大於一種以上字母出現 y 次,則代表我們刪掉任何字母都會使得條件不符合。因為一定會有一種字母是出現 y - 1 次(而 y == 1 的情況已經在上面被處理掉了)。因此回傳假;
如果出現 x 次的字母種類大於一個而同時出現 y 次的字母也同樣大於一個,則代表我們沒辦法只藉由刪掉一個字母把所有出現 x 次的字母都變成只出現 y 次。因此回傳假;
如果 x - 1 != y,則代表我們就算刪掉一個出現最多次的字母,也沒辦法使得其出現次數降到 y。因此回傳假;
如果上述都不符合,則代表我們藉由刪除恰好一個出現 x 次的恰好一種字母,來將其降至只出現 y 次。因此回傳真。
此次分享到此為止,如有任何更加簡潔的想法或是有說明不清楚之地方,也煩請各位大大撥冗討論。