leetcode 242.Valid Anagram

242. Valid Anagram

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

Example 1:

Input: s = “anagram”, t = “nagaram”
Output: true

Example 2:

Input: s = “rat”, t = “car”
Output: 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?

来源:力扣(LeetCode)
链接:https://leetcode-cn.com/problems/valid-anagram
著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。
  分析:
  这道题考的是数组的问题,首先解释以下什么是字母异位词(Anagram)。如题目所述,字符串s里面含有3个a,1个n,1个g,一个r和一个m,在字符串t中含有相同的字母,并且对应字符的数目相同,因此两者互为异位词。最容易想到的一种解法就是初始化一个长度为128的辅助数组全0,用字符作为下标,首先遍历字符串s,并对s中出现的字符进行计数,之后遍历t再因此减去计数,当s和t互为异同词的时候,辅助数组值依然全0,否则不互为异位词。
  C++:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution {
public:
bool isAnagram(string s, string t) {
int arr[128] = {0};
int len1 = s.length(), len2 = t.length();
if(len1 != len2) return false;
for(int i = 0; i < len1; i++){
arr[s[i]]++;
arr[t[i]]--;
}
for(char k = 'a'; k <= 'z'; k++){
if(arr[k] != 0)
return false;
}
return true;
}
};

  使用C++中STL的hashmap:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution {
public:
bool isAnagram(string s, string t) {
if(s.length() != t.length()) return false;
unordered_map <char, int> mymap;
for(char ch : s)
mymap[ch]++;
for(char ch : t){
if(mymap[ch] > 0)
mymap[ch]--;
else
return false;
}
return true;
}
};

  发现使用hashmap实现更慢,这是为什么呢?