242.有效的字母異位詞

數(shù)組、set、map，數(shù)組是比較高效查找的

函數(shù)功能

判斷字符串 s 和 t 是否互為字母異位詞。如果它們包含相同的字符且每個(gè)字符出現(xiàn)的次數(shù)也相同，那么它們互為字母異位詞。

代碼邏輯

1. 長度檢查：

   if (s.length !== t.length) return false;

   如果 s 和 t 的長度不相等，它們不可能是字母異位詞，直接返回 false。

2. 初始化計(jì)數(shù)器數(shù)組：

   const resSet = new Array(26).fill(0); 
   const base = "a".charCodeAt();

   • resSet 是一個(gè)長度為 26 的數(shù)組，用于存儲每個(gè)小寫字母的出現(xiàn)次數(shù)（假設(shè) s 和 t 只包含小寫字母）。
   • base 存儲了字母 'a' 的 ASCII 碼值，用于將字母轉(zhuǎn)換為數(shù)組索引。

3. 統(tǒng)計(jì) s 中字符出現(xiàn)次數(shù)：

   for (const i of s) { resSet[i.charCodeAt() - base]++; }

   遍歷字符串 s，使用 charCodeAt() 函數(shù)獲取每個(gè)字符的 ASCII 碼值，然后根據(jù) base 計(jì)算出索引，增加 resSet 中相應(yīng)位置的計(jì)數(shù)。

4. 驗(yàn)證 t 中的字符：

   for (const i of t) 
   { if (!resSet[i.charCodeAt() - base]) return false; 
   resSet[i.charCodeAt() - base]--; }

   • 遍歷字符串 t，對于每個(gè)字符，檢查 resSet 中對應(yīng)位置的計(jì)數(shù)。如果計(jì)數(shù)為 0，則表示 t 中有一個(gè)在 s 中不存在的字符，或者字符出現(xiàn)次數(shù)不匹配，返回 false。
   • 減少 resSet 中相應(yīng)位置的計(jì)數(shù)。

5. 返回結(jié)果：

   return true;

   果代碼執(zhí)行到這里，說明 s 和 t 是字母異位詞，返回 true。

總結(jié)

這個(gè)函數(shù)通過計(jì)數(shù)每個(gè)字符的出現(xiàn)次數(shù)，來判斷兩個(gè)字符串是否互為字母異位詞。由于只用了一個(gè)固定長度的數(shù)組，它在處理只包含小寫字母的字符串時(shí)非常高效。

49字母異位詞

示例 1: 輸入 ["eat", "tea", "tan", "ate", "nat", "bat"]

1. 初始化哈希表：

   • 創(chuàng)建一個(gè)空的 Map 對象 map。

2. 遍歷字符串?dāng)?shù)組：

   • 對于每個(gè)字符串 str 在數(shù)組 ["eat", "tea", "tan", "ate", "nat", "bat"] 中，執(zhí)行以下步驟：

     • "eat"：

       • 分解、排序并重新組合："eat" -> ["e", "a", "t"] -> ["a", "e", "t"] -> "aet"
       • map.has("aet") 返回 false（因?yàn)?"aet" 還不在 map 中），所以執(zhí)行 map.set("aet", []) 并添加 "eat" 到 "aet" 鍵對應(yīng)的數(shù)組中。

     • "tea"：

       • 同樣地，"tea" 排序后變?yōu)?"aet"。
       • map.has("aet") 返回 true（因?yàn)?"aet" 已存在），所以直接將 "tea" 添加到 "aet" 鍵對應(yīng)的數(shù)組中。

     • "tan"：

       • "tan" 排序后變?yōu)?"ant"。
       • map.has("ant") 返回 false，所以執(zhí)行 map.set("ant", []) 并添加 "tan" 到 "ant" 鍵對應(yīng)的數(shù)組中。

     • "ate"：

       • "ate" 排序后也是 "aet"。
       • 再次將 "ate" 添加到 "aet" 鍵對應(yīng)的數(shù)組中。

     • "nat"：

       • "nat" 排序后變?yōu)?"ant"。
       • 將 "nat" 添加到 "ant" 鍵對應(yīng)的數(shù)組中。

     • "bat"：

       • "bat" 排序后變?yōu)?"abt"。
       • map.has("abt") 返回 false，所以執(zhí)行 map.set("abt", []) 并添加 "bat" 到 "abt" 鍵對應(yīng)的數(shù)組中。

3. 提取并返回結(jié)果：

   • 使用 Array.from(map.values()) 將 map 中的所有值（即分組后的字符串?dāng)?shù)組）轉(zhuǎn)換為一個(gè)數(shù)組。
   • 返回的數(shù)組是：[["eat", "tea", "ate"], ["tan", "nat"], ["bat"]]。

結(jié)果解釋

函數(shù) groupAnagrams 將每個(gè)字符串按字母排序后，使用排序結(jié)果作為鍵來分組所有字母異位詞。最終返回的數(shù)組包含了分組好的字母異位詞數(shù)組，每個(gè)子數(shù)組包含所有字符集相同的原始字符串。在這個(gè)例子中，"eat"、"tea" 和 "ate" 互為字母異位詞，因此它們被分組在一起，同理可得其他分組。

438.找到字符串中所有字母異位詞?

1. 初始化兩個(gè)計(jì)數(shù)器數(shù)組：pCount 和 sCount 分別用于存儲 p 和窗口內(nèi)字符串的字符計(jì)數(shù)。

2. 遍歷 p：對 p 中的每個(gè)字符進(jìn)行計(jì)數(shù)。

3. 滑動窗口：遍歷字符串 s，同時(shí)更新 sCount 數(shù)組來計(jì)算窗口內(nèi)各字符的出現(xiàn)次數(shù)。

4. 窗口大小與 p 相等時(shí)：比較 sCount 和 pCount。如果兩者完全一致，將左指針的位置加入結(jié)果數(shù)組。

5. 移動窗口：右指針每向右移動一次，左指針也相應(yīng)地向右移動一次，以保持窗口大小不變。

這種方法通過在 s 上滑動一個(gè)固定大小的窗口并比較字符出現(xiàn)次數(shù)，有效地找出了所有 p 的異位詞的起始索引。

?