242. Valid Anagram

问题

Given two strings s and t, write a function to determine if t is an anagram of s.

Note:
You may assume the string contains only lowercase alphabets.

Follow up:
What if the inputs contain unicode characters? How would you adapt your solution to such case?

例子

s = "anagram", t = "nagaram", return true.
s = "rat", t = "car", return false.

分析

Anagram的意思是“由颠倒字母顺序而构成的字”，即原单词的一个全排列(Permutation)。

可以使用一个256大小的数组统计两个单词的字母的出现频率：在s中出现加1，在t中出现减1。

如果要考虑unicode，则要通过首字节的模式来判断下一个字符是单字符字母还是双字符字母。

要点

• bucket思想；
• 两个单词可以共用一组bucket，减少空间占用。

时间复杂度

O(n)

空间复杂度

O(1)

代码

class Solution {
public:
    bool isAnagram(string s, string t) {
        if (s.length() != t.length()) return false;
        char map[256] = {0};
        for (int i = 0; i < s.length(); i++) {
            map[s[i]]++;  
            map[t[i]]--;
        }
        for (int i = 0; i < 256; i++)
            if (map[i] != 0)
                return false;
        return true;
    }
};