1. 題目描述

給定兩個僅包含小寫字母的字符串 s 和 t ，編寫一個函數來判斷 t 是否是 s 的 字母異位詞。

字母異位詞定義：兩個字符串包含的字母種類和數量完全相同，但順序可以不同（例如 “listen” 和 “silent”）。

原題鏈接：[242]

2. 解題思路

使用哈希表的方式實現。
哈希表底層可以用一個數組實現，將兩個字符串的字符映射到哈希表的每個索引中，然后依次對比兩個哈希表內的元素是否一致即可。

關鍵在于如何構建哈希函數。

根據題目，兩個字符串都只包含小寫字母，最多26個小寫字母，所以構建哈希表的大小為26即可，字母a放到索引0，字母z放到索引25，依次填入。
而如何將字母放到對應的索引中？ 根據代碼原理，字符本質上是基于 ASCII 碼值的整數，a到z對應是連續的ASCII 碼值，所以 ‘a’ - ‘a’是0，‘b’ - ‘a’是1，以此類推可以得到a的索引是0，b的索引是1，c的索引是2…這樣就可以將字符串內的字符按規則填入哈希表的對應索引中進行比較。

3. C語言實現

3.1 雙哈希表

bool isAnagram(char* s, char* t) {int lens = strlen(s), lent = strlen(t);if(lens != lent)return false;int map1[26] = {0} , map2[26] = {0};for(int i = 0; i < lens; i++){map1[s[i] - 'a'] += 1;map2[t[i] - 'a'] += 1;}for(int i = 0; i < 26; i++){if(map1[i] != map2[i]){return false;}}return true;
}

• 首先判斷兩個數組的長度是否相等，長度不相等肯定不是字母異位詞。
• 定義兩個哈希表map1和map2，長度設置為26，初始化全為0。
• for循環遍歷兩個字符串s和t，s[i] - 'a’即表示字符串s中第i個位置的字符該對應于哈希表map1的第幾個索引位置，得到索引之后在map1的相應索引處加1，代表該處有一個元素。
• map2同理。
• for循環遍歷map1和map2的26個索引，檢查兩個哈希表是否一致，不一致則返回false表示兩個字符串不是有效的字母異位詞。

3.2 單哈希表

上面是用兩個哈希表對應兩個字符串，遍歷到字符時在對應的哈希表內加1計數；可以優化一下，使用全為0的單哈希表，遍歷s時在哈希表對應索引增加計數，遍歷t時在哈希表對應索引減少技術，最后檢查哈希表是不是全為0，如果有的索引還有計數，則說明兩個字符串含有數量不一樣的字符，不是有效的字母異位詞，很好理解。

bool isAnagram(char* s, char* t){int lens = strlen(s);int lent = strlen(t);if(lent != lens)return false;int map[26] = {0};for(int i = 0; i < lens; i++){map[s[i] - 'a'] += 1;}for(int i = 0; i < lens; i++){map[t[i] - 'a'] -= 1;}for(int i = 0; i < 26; i++){if(map[i] != 0)return false;}return true;
}