1941. Check if All Characters Have Equal Number of Occurrenc

英文版點我｜中文版點我

↑看個小廣告，支持好內容↑

❶ Hash Table (索引、桶子)

所有字符必須出現一樣多次，有關計數的任務，就交給索引吧！先遍歷字串 s 做統計，再檢查索引共有幾種值，時間花費 O(2n)。

小寫字母就 26 個，因此索引頂多就 26 個 key，空間複雜度 O(26)→O(1)。由於關注的是計數頻率，我們也可開一個長度 26 的陣列 (我習慣稱它桶子)，結果會相同：

// s="abacbc"

1. 索引
	- 計數結果：map[a]=2, map[b]=2, map[c]=2
	- 頻率陣列：Object.values(map)	 // [2,2,2]

2. 桶子
	- 計數結果：arr[0]=2, arr[1]=2, arr[2]=2
	- 頻率陣列：arr.filter(x=>x>0)  //​ [2,2,2]

次數必須一致，轉成集合檢查 new Set(頻率陣列).size=1 就行了。

❷ Follow-Up: Counting

雖然這題很好 pass，但我蠻好奇有沒有不靠索引的解法 XD

假設把字串排成 aabbcc，當一看到 b 就能肯定 a 出現完畢，再來結算其頻率是否有重複，邏輯上似乎說得通：

// 假設ｓ已依字母順序排好
​
var areOccurrencesEqual = function(s) {
    let freq=0, curr=1;

    for(let i=1; i<s.length; i++){
        if(s[i]==s[i-1]){
            curr++;​
        }else{
            // 以首個字母的次數作為基準
            if(freq==0){freq=curr);
            // 若出現頻率與基準值不同 => false
            if(freq!=curr){return false};
            curr=1;
        }
    }
    // 檢查最後一個字母，並排除單一字母的狀況
    return freq==curr || freq==0;
};

撇除掉排列字母，這樣只要跑一次迴圈就能完成，有沒有挺像之前按計數器的感覺呢？遵循相似的思維，這題確實也能用雙指針來解沒錯！今天篇幅夠了，就當回家作業吧 (X

• 本題分類標籤：Hash Table、String、Counting
• 本題正解率＝77.0％

❤️ 若內容對你實用，歡迎追蹤本專題，或小額贊助支持～
⭐ 這是我的第 16 篇刷題筆記，完整解題索引看這裡 → Here