題目敘述

題目難度: Easy
題目敘述: 題目要求給定兩個字串 s 與 t，若 t 為 s 的 Anagram，則回傳 true，若不是則回傳 false

Anagram 代表兩個單字裡面組成的字母和數量是完全一樣的，簡單來說 Anagram 就是由A單字重新排列組合成一個B單字。

解法

一開始的想法

這次的想法一樣是建立 HashTable，所以一開始的想法如下:

迭代 s，建立 HashTable
迭代 t，依序檢查字母是否有出現在 HashTable，進行比對
迭代完畢後，若全部匹配則回傳True
若無則否

我的解法

class Solution {
public:
    bool isAnagram(string s, string t) {
        //character, times
        unordered_map<char, int> Dict;

        if (s.length() != t.length()) {
            // If the lengths are different, they cannot be anagrams
            return false;
        }

        // Build the dictionary
        for(int i=0; i< s.length(); i++){
            Dict[s[i]]++;
        }

        for (int i=0; i<t.length(); i++){
            // Match
            if (Dict.find(t[i]) != Dict.end()){
                Dict[t[i]]--;
                if(Dict[t[i]] == 0){
                    Dict.erase(t[i]);
                }
            }
            else{  //Not match
                return false;
            }
        }
        
        if(!Dict.empty()){
            return false;
        }
        else{
            return true;
        }

    }
};

說明

首先透過 unordered_map 建立了一個 Hash table
若 s 與 t 長度不一致，可以提前回傳　false
迭代 ｓ　建立 Hash table，並且 Key 會是 s 中出現的字母，value 會是出現次數
迭代 t，透過在 Dict.find() 中迭代 t 的字母，查看是否對應的 key 存在於 Hash Table 中
如果有，則該字母的對應將次數減少 (Dict[t[i]]--;)
如果已經減到0次，則將該key-value pair 從 Table 中移除
如果在 table 中沒找到 t 中的字母，則回傳　false
最後若 table 不是空的，就代表t沒有完全匹配s，則一樣回傳 false，反之則回傳 true

執行結果

其他做法

class Solution {
public:
    bool isAnagram(string s, string t) {
    
        if (s.length() != t.length()) {
            return false;
        }

        // A count vector with length 26 with init value 0
        // Count only lowercase letters 
        vector<int> count(26,0);

        //build dictionary
        for (int i=0; i< s.length(); i++){
            count[s[i] - 'a']++;
        }

        for(int i=0; i < t.length(); i++){
            count[t[i]-'a']--;
        }

        for(auto it=count.begin(); it!=count.end(); it++){
            if(*it != 0){
                return false;
            }
        }
        return true;
    }
};