前往
大廳
主題

LeetCode - 2423. Remove Letter To Equalize Frequency 解題心得

Not In My Back Yard | 2023-08-17 12:00:03 | 巴幣 0 | 人氣 95

題目連結:


題目意譯:
你被給定一個索引值從 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 次。因此回傳真。




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

創作回應

更多創作