別只知道暴力循環！我從用戶名校驗功能中領悟到的高效字符集判斷法 😎

大家好，日常開發中，我們經常會遇到一些看似不起眼，卻能成為性能瓶頸的小模塊。今天，我想和大家分享一個我親身經歷的故事，關于如何從一個簡單的“用戶名合法性校驗”功能，一步步挖掘出三種不同層次的算法解法，最終get到性能優化的精髓。

我遇到了什么問題

事情是這樣的，我正在負責一個新項目的用戶注冊模塊。產品經理（PM）跑過來對我說：“為了系統的安全和統一，我們規定新注冊的用戶名，只能包含我們指定的一組字符。這組字符未來可能會在后臺調整。”

聽起來是個小需求嘛，不就是個字符串校驗？我當時想。

PM接著補充道：“后臺會有個功能，可以批量導入一批用戶名，我們需要快速地篩選出所有合法的用戶名。”

這個場景就變得有意思了。我需要一個規則集（allowed 字符串）去校驗一大批待測字符串（words 數組）。如果每次校驗一個單詞，都去遍歷一次規則集，當單詞數量和長度上來后，性能開銷會非常大。

這讓我想起了 LeetCode 上的這道題，簡直就是對我這個場景的完美抽象：

1684. 統計一致字符串的數目

給你一個由不同字符組成的字符串 allowed 和一個字符串數組 words 。如果一個字符串的每一個字符都在 allowed 中，就稱這個字符串是 一致字符串 。請你返回 words 數組中 一致字符串 的數目。

在動手編碼前，我們先來仔細品味一下題目的“提示”：

• 1 <= words.length <= 10^4, 1 <= words[i].length <= 10: 單詞數量不少，但每個單詞都不長。這告訴我們，算法的效率重點應該放在如何快速判斷“單個字符”是否合法上，而不是糾結于單詞長度。
• 1 <= allowed.length <= 26, allowed 中的字符 互不相同, 只包含小寫英文字母: 這是最重要的三條信息！ 它把問題從一個通用的字符串匹配，降維到了一個固定大小（26個字母）的集合問題上。這是我們施展優化“魔法”的關鍵。

好了，背景介紹完畢，讓我們看看我是如何用三套“組合拳”來解決這個問題的。

我是如何用算法“組合拳”解決的

解法一：哈希集合（HashSet），萬能的“存在性”檢查器

這是我腦海里冒出的第一個想法，也是最符合直覺的解法。要反復檢查一個字符在不在 allowed 里，如果每次都用 String.contains()，效率太低。更好的辦法是把 allowed 的字符先存到一個查詢飛快的數據結構里。HashSet 就是為此而生的！

先把所有“合法”的字符都請進一個 HashSet，它就像一個VIP俱樂部的門禁系統。然后，對于每一個待校驗的用戶名，我們檢查它的每個字符是不是這個俱樂部的會員。

import java.util.HashSet;
import java.util.Set;/** 思路：使用哈希集合。將 allowed 字符串的字符存入 HashSet，以實現 O(1) 的快速查找。* 然后遍歷每個單詞，檢查其所有字符是否都在 HashSet 中。* 時間復雜度：O(L + S)，其中 L 是 allowed 的長度，S 是 words 中所有字符的總數。* 空間復雜度：O(L)，由于 L<=26，可視為 O(1)。*/
class Solution {public int countConsistentStrings(String allowed, String[] words) {// 1. 預處理，構建“VIP俱樂部”// 為什么用 HashSet？因為它提供了平均時間復雜度為 O(1) 的 contains() 方法，// 對于需要頻繁檢查“某元素是否存在于集合中”的場景，它是最理想的選擇。// 比起 List 的 O(L) 查找，簡直是降維打擊。Set<Character> allowedSet = new HashSet<>();for (char c : allowed.toCharArray()) {allowedSet.add(c);}int consistentCount = 0;// 2. 遍歷所有待校驗的用戶名for (String word : words) {boolean isConsistent = true;// 3. 檢查用戶名的每個字符for (char c : word.toCharArray()) {// 如果在“VIP俱樂部”里查不到這個字符，說明是非法用戶，直接標記并“拉黑”if (!allowedSet.contains(c)) {isConsistent = false;break; // 重要的優化：一旦發現不合法的，立即停止對當前單詞的檢查！}}// 如果這個用戶名所有字符都通過了檢查，計數器加一if (isConsistent) {consistentCount++;}}return consistentCount;}
}

復雜度

時間復雜度：O(L + S)。L 是 allowed 的長度，S 是 words 中所有字符的總數。構建 HashSet 的時間是 O(L)。之后遍歷所有單詞的所有字符，總字符數為 S，每次查詢是 O(1)，所以檢查部分是 O(S)。總計 O(L + S)。

空間復雜度：O(L)。HashSet 需要存儲 allowed 中的字符。因為題目限制 L <= 26，所以空間復雜度可以認為是常數級別的 O(1)。

這個解法又穩又準，代碼清晰，足以應對大多數場景。但當我看到提示里的“26個小寫字母”時，一個念頭閃過：我真的需要 HashSet 這個“重型武器”嗎？有沒有更輕量、更快的辦法？😉

解法二：布爾數組，小范圍數據的“降維打擊”

HashSet 很好，但它內部有哈希計算、沖突處理等機制，有一定開銷。既然我們已經知道所有字符都在’a’到’z’這個小范圍內，就可以用一個簡單的數組來創建一個更快的“門禁系統”。

我們可以創建一個長度為26的布爾數組，每個位置對應一個字母。array[0] 代表 ‘a’，array[1] 代表 ‘b’，以此類推。如果 allowed 里有 ‘c’，我們就把 array[2] 設為 true。檢查時，只需要看對應位置是不是 true 就行了，這是最純粹的 O(1) 操作！

/** 思路：使用布爾數組模擬哈希。利用字符集限定在26個小寫字母的特性，* 創建一個長度為26的布爾數組作為查找表，比 HashSet 更高效。* 時間復雜度：O(L + S)，但常數時間更小。* 空間復雜度：O(1)，數組大小固定為26。*/
class Solution {public int countConsistentStrings(String allowed, String[] words) {// 1. 預處理，構建一個超快的“字母通行證”// 為什么用 boolean 數組？因為當鍵的范圍已知且很小時（26個字母），// 數組提供了最快的直接尋址訪問（真正的 O(1)），避免了 HashSet 的哈希計算和潛在沖突開銷。// c - 'a' 這個操作是精髓，它能巧妙地把字符映射到 0-25 的索引上。boolean[] isAllowed = new boolean[26];for (char c : allowed.toCharArray()) {isAllowed[c - 'a'] = true;}int consistentCount = 0;outerLoop: // 使用標簽可以更清晰地跳出外層循環，直接檢查下一個單詞for (String word : words) {for (char c : word.toCharArray()) {// 如果“通行證”上這個字母沒蓋章，說明不合法if (!isAllowed[c - 'a']) {continue outerLoop; // 直接跳到下一個單詞的檢查}}// 如果一個單詞的內層循環能正常走完，說明它是合法的consistentCount++;}return consistentCount;}
}

復雜度

時間復雜度：O(L + S)。分析同上。但由于數組訪問是直接內存尋址，它的實際運行速度通常會比 HashSet 快。

空間復雜度：O(1)。isAllowed 數組的大小是固定的26，不隨輸入規模變化，是純粹的常數空間。

這個解法是我當時“恍然大悟”的瞬間！它讓我明白了，充分利用題目給定的約束條件，是算法優化的不二法門。這個方法已經非常高效了，但我還想挑戰一下自己，有沒有辦法把空間再壓榨一下？

解法三：位運算（Bitmask），高手的極簡主義

布爾數組 [true, true, false, ...] 本質上不就是一串二進制 110... 嗎？既然如此，我為什么不直接用一個整數來表示這26個狀態位呢？一個 int 類型有32位，足夠放下26個字母的“通行證”了！

這就是位運算的魅力。我們可以用一個整數的二進制位來代表集合。第0位是1，代表’a’合法；第1位是1，代表’b’合法……

• 添加字符：用“按位或 |”操作。
• 檢查字符：用“按位與 &”操作。

/** 思路：位運算。將 allowed 字符串表示為一個位掩碼（bitmask），然后檢查* 每個單詞的每個字符對應的位是否在該掩碼中為1。這是空間和時間效率都極高的做法。* 時間復雜度：O(L + S)。* 空間復雜度：O(1)。*/
class Solution {public int countConsistentStrings(String allowed, String[] words) {// 1. 預處理，構建一個整數版的“通行證”// 為什么用 int 做位掩碼？因為它緊湊、高效。26個字母的狀態剛好可以用一個32位整數表示。// `1 << (c - 'a')` 生成一個只有 c 對應位是 1 的數字（例如 c='b', 結果是二進制的10）。// `|=` (按位或賦值) 將這個位設置為1，而不影響其他位。int allowedMask = 0;for (char c : allowed.toCharArray()) {allowedMask |= (1 << (c - 'a'));}int consistentCount = 0;outerLoop:for (String word : words) {for (char c : word.toCharArray()) {// 檢查字符 c 的“通行證”位是否為1// `(allowedMask & (1 << (c - 'a')))` 會提取出 c 對應的位。// 如果結果是 0，說明 allowedMask 在這一位上是0，即字符不合法。if ((allowedMask & (1 << (c - 'a'))) == 0) {continue outerLoop; // 驗證失敗，檢查下一個單詞}}consistentCount++;}return consistentCount;}
}

復雜度

時間復雜度：O(L + S)。分析同上。位運算直接在CPU層面執行，通常是所有解法中實際運行最快的。

空間復雜度：O(1)。只用了一個額外的 int 變量，空間利用達到了極致。

這個解法雖然代碼看起來有點“黑話”，但它展示了對計算機底層工作原理的深刻理解。在追求極致性能的場景下，位運算是你的屠龍寶刀！

舉一反三：這個思想還能用在哪？

這個“預處理查詢集”的思想在開發中無處不在：

• API網關：校驗請求參數是否在允許的枚舉值范圍內。
• 文件上傳：檢查上傳文件的后綴名是否在白名單中（如 .jpg, .png, .gif）。
• 敏感詞過濾：將敏感詞庫預處理成高效的查找結構（如Trie樹），快速判斷文本中是否包含敏感詞。

練練手，更熟練

如果你對這類問題產生了興趣，不妨挑戰一下這些“兄弟”題目，它們都能用上類似的思路：

• 771. 寶石與石頭：本題的簡化版，絕佳的入門練習。
• 242. 有效的字母異位詞：同樣使用數組作為哈希表來統計字符頻率。
• 389. 找不同：位運算解法在此題中大放異彩。

希望我這次從真實項目到算法優化的心路歷程能給你帶來一些啟發。記住，優雅的解決方案，往往源于對問題本質和約束條件的深刻洞察。下次再遇到類似問題，別只知道暴力循環啦！😉

解法對比

特性	解法一 (HashSet)	解法二 (布爾數組)	解法三 (位運算)
核心思想	通用哈希集合查找	數組直接尋址模擬哈希	整數位表示集合
代碼簡潔度	高，API直觀易用	中，邏輯清晰	低，需要理解位運算
執行效率	高效	非常高效（優于HashSet）	極致高效（硬件級優化）
時間復雜度	O(L + S)	O(L + S)	O(L + S)
空間復雜度	O(L) (可視為O(1))	O(1) (固定26)	O(1) (固定1個int)
普適性	高，可用于任何類型元素	低，僅限于鍵可映射為連續整數	低，僅限于鍵空間極小