leetcode 242. Valid Anagram

题目

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

For example, s = “anagram”, t = “nagaram”, return true. s = “rat”, t = “car”, return false.

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?

anagram是一种文字游戏，即一个字符串能不能通过字符调换位置得到另一个字符串，从给的例子里面就很容易理解。

解题思路

这道题看到，首先排除了最暴力的一个个字符比对，时间复杂度太高。对于字符串，我们常用的是hash table，这道题中我们可以统计各个字符出现的频次，如果两个字符串之间每个字符出现次数都一样，那必然可以通过调换位置得到。 由于题目中规定的是小写字母用例，所以这道题用一个int[26]的数组统计频次即可。 再思考一下，两个字符串首先要一样长，另外让空间开销尽量小。这道题只需要一个数组进行统计即可，循环时，一个字符串加，一个字符串减。若为anagram，则数组里面每个元素都应该为0。代码见方法二。

AC代码如下

方法一：

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

方法二：

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

总结

题目拓展部分说，如果把这个算法扩展到unicode字符集，怎样修改。这样的话，用int数组可能不太方便，使用unordered_map更好，核心思想不改变。代码如下：

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