Valid Anagram – LeetCode 242
Problem
Description
Given two strings s and t, write a function to determine if t is an anagram of s.
Example
For example,
s = “anagram”, t = “nagaram”, return true.
s = “rat”, t = “car”, return false.
Answer
Original
Code
1
2
3
4
5
6
7
8
9
10
11
12
13
| class Solution {
public:
bool isAnagram(string s, string t) {
int cnt[26] = {};
for(unsigned i = 0; i != s.size(); ++i)
++cnt[s[i]-'a'];
for(unsigned i = 0; i != t.size(); ++i)
--cnt[t[i]-'a'];
for(unsigned i = 0; i != 26; ++i)
if(cnt[i]) return false;
return true;
}
};
|
思路
使用数组简单存储出现的次数。时间复杂度$O(n)$，空间复杂度$O(n)$。
耗时$9$ ms，排名$33.23\%$
Better
思路
这个方法只是展示一下，使用排序来处理，然后一次遍历查找不对的地方。时间复杂度$O(nlog_{2}{n})$，空间复杂度$O(1)$。
耗时$23$ ms，排名$86.44\%$
Code
1
2
3
4
5
6
7
8
9
10
11
| class Solution {
public:
bool isAnagram(string s, string t) {
if(s.size() != t.size()) return false;
sort(s.begin(),s.end());
sort(t.begin(),t.end());
for(unsigned i = 0; i != s.size(); ++i)
if(s[i] != t[i]) return false;
return true;
}
};
|