340-Leetcode 有效的字母异位词

方法一：排序

class Solution 
{
public:
	bool isAnagram(string s, string t)
	{
		int len1 = s.size();
		int len2 = t.size();
		if (len1 != len2)return false;
		sort(s.begin(), s.end());
		sort(t.begin(), t.end());

		return s == t;
	}
};
int main()
{
	Solution A;
	cout << A.isAnagram("rat","car") << endl;
	return 0;
}

时间复杂度：O(nlogn)，其中 n 为 s 的长度。排序的时间复杂度为O(nlogn)，比较两个字符串是否相等时间复杂度为 O(n)，因此总体时间复杂度为 O(nlogn+n)=O(nlogn)

空间复杂度：O(logn)。排序需要 O(logn) 的空间复杂度。注意，在某些语言（比如 Java & JavaScript）中字符串是不可变的，因此我们需要额外的 O(n) 的空间来拷贝字符串。但是我们忽略这一复杂度分析，因为：
①这依赖于语言的细节；
②这取决于函数的设计方式，例如，可以将函数参数类型更改为 char[]。

方法二：哈希表

class Solution {
public:
    bool isAnagram(string s, string t) {
int len1 = s.size();
		int len2 = t.size();
		if (len1 != len2)return false;
		vector table(26, 0);
		for (auto& ch : s)
		{
			++table[ch - 'a'];
		}
		for (auto &ch : t)
		{
			if (--table[ch - 'a'] < 0)
			{
				return false;
			}
		}	
		return true;
    }
};

时间复杂度：O(n)，其中 n 为 s 的长度。
空间复杂度：O(S)，其中 S 为字符集大小，此处 S=26