题目

给定两个字符串 s 和 t ，编写一个函数来判断 t 是否是 s 的字母异位词。
注意：若 s 和 t 中每个字符出现的次数都相同，则称 s 和 t 互为字母异位词。

示例 1:

输入: s = "anagram", t = "nagaram"
输出: true

示例 2:

输入: s = "rat", t = "car"
输出: false

提示:

• 1 <= s.length, t.length <= 5 * 104

• s 和 t 仅包含小写字母

  
  进阶: 如果输入字符串包含 unicode 字符怎么办？你能否调整你的解法来应对这种情况？

  解题方法

  String排序比较法

  对排序后的s和t逐元素比较。
  时间复杂度O(nlogn)，空间复杂度O(logn)。

  class Solution {
  public:
    bool isAnagram(string s, string t) {
        sort(s.begin(), s.end());
        sort(t.begin(), t.end());
        if(s==t)    return true;
        else return false;
    }
  };

  哈希表(map)

  构建map判断s和t中元素是否相同。
  时间复杂度O(n)，空间复杂度O(n)。

  class Solution {
  public:
    bool isAnagram(string s, string t) {
        unordered_map<char, int> map;
        if(s.size()!=t.size()) return false;
        for(int i = 0;i<s.size();i++){
            map[s[i]]++;
            map[t[i]]--;
        }
        for(auto i = map.begin(); i!=map.end(); i++) {
            if(i->second!=0)    return false;
        }
        return true;
    }
  };

  哈希表(数组）

  构建哈希函数H(char)= char-'a'。
  通过大小为26的数组即可完成字母数字统计。
  时间复杂度O(n)，空间复杂度O(s)，对小写字母集s为26。

  class Solution {
  public:
    bool isAnagram(string s, string t) {
        int num[26] = {0};
        if (s.size()!=t.size()) return false;
        for (int i = 0; i<s.size(); i++) {
            num[s[i]-'a']++;
            num[t[i]-'a']--;
        }
        for (int i = 0; i<26; i++) {
            if (num[i]!=0)  return false;
        }
        return true;
    }
  };