傳送門：力扣

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

注意：若?s 和 t?中每個字符出現的次數都相同，則稱?s 和 t?互為字母異位詞。

示例?1:輸入: s = "anagram", t = "nagaram"? ? 輸出: true
示例 2:輸入: s = "rat", t = "car"? ?輸出: false

用暴力枚舉兩層for循環的時間復雜度是O(n*n)

用哈希表的時間復雜度是O(1)

用哈希表來保存s字符串所有字符的出現次數，有點類似之前接觸的桶排序思想。再進行t字符串所有字符的出現。操作是做兩個for循環去分別循環s，t字符串。s字符串出現的所有字符hash保存自增，t字符串出現的所有字符在hash中進行自減操作，之后在單對hash表檢索是否有元素不是0.

大開眼界的是string是用字符數組封裝的，所以也可以直接使用? 字符串名稱.size（）來獲取字符串長度。非常方便。

#define _CRT_SECURE_NO_WARNINGS 1 #include<iostream> using namespace std;class Solution { public:bool isAnagram(string s, string t) {int record[26] = { 0 };for (int i = 0; i < s.size(); i++) {// 并不需要記住字符a的ASCII，只要求出一個相對數值就可以了record[s[i] - 'a']++;}for (int i = 0; i < t.size(); i++) {record[t[i] - 'a']--;}for (int i = 0; i < 26; i++) {if (record[i] != 0) {// record數組如果有的元素不為零0，說明字符串s和t 一定是誰多了字符或者誰少了字符。return false;}}// record數組所有元素都為零0，說明字符串s和t是字母異位詞return true;} }; int main() {Solution solution;cout << solution.isAnagram("anagram", "nagaram") << endl;cout << solution.isAnagram("cat", "mat") << endl; }

總結

以上是生活随笔為你收集整理的Leetcode 242.有效的字母异位词（哈希表）的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。