前往
大廳
主題

LeetCode - 1897. Redistribute Characters to Make All Strings Equal 解題心得

Not In My Back Yard | 2021-09-27 00:00:06 | 巴幣 0 | 人氣 107

題目連結:


題目意譯:
你被給定一字串陣列 words(索引值從 0 開始)。

在一次操作中,選定兩個相異索引值 i 和 j ,其中 words[i] 為非空字串然後移動任一字元到 words[j] 的任一位置。

回傳真(True)如果你可以藉由任意次操作使得 words 中的每個字串相等;反之,回傳假(False)。

限制:
1 ≦ words.length ≦ 100
1 ≦ words[i].length ≦ 100
words[i] 由小寫英文字母組成。



範例測資:
範例 1:
輸入: words = ["abc","aabc","bc"]
輸出: true
解釋: 移動 words[1] 中的第一個 'a' 到 words[2] 的前端,令 words[1] = "abc" 且 words[2] = "abc" 。
現在所有字串都等於 "abc" ,所以回傳真。

範例 2:
輸入: words = ["ab","a"]
輸出: false
解釋: 無法使用操作將所有字串變為相同。


解題思維:
令 n 為 words.length 。

我們可以統計 words 中每種字元的出現次數。當有任何字元的出現總次數無法被 n 整除時,則代表我們無法將該字元平均地分配到所有字串中,也就不可能讓所有字串相等;而相反地,如果每種字元都可以被 n 整除,則我們可以藉由有限次的操作將所有字元平均分布於所有字串中,然後調整到讓所有字串相等。




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

創作回應

更多創作