242. Valid Anagram

  • 45.4%

https://leetcode.com/problems/valid-anagram/?tab=Description

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

1
2
3
For example,
s = "anagram", t = "nagaram", return true.
s = "rat", t = "car", return false.

Note:

You may assume the string contains only lowercase alphabets.


https://discuss.leetcode.com/topic/20303/2-c-solutions-with-explanations

2 C++ Solutions with Explanations

方法一:

Hash Table

This idea uses a hash table to record the times of appearances of each letter in the two strings s and t. For each letter in s, it increases the counter by 1 while for each letter in t, it decreases the counter by 1. Finally, all the counters will be 0 if they two are anagrams of each other.

The first implementation uses the built-in unordered_map and takes 36 ms.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
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;
}
};

方法二:

Since the problem statement says that “the string contains only lowercase alphabets”, we can simply use an array to simulate the unordered_map and speed up the code. The following implementation takes 12 ms.

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

我的实现:

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 m = s.size();
int n = t.size();
if(n<m)
return false;
vector<int> tmp(26, 0);
for(auto str:s)
tmp[str-'a']++;
for(auto str:t){
if(tmp[str-'a']--==0)
return false;
}
return true;
}
};

方法三:

Sorting

For two anagrams, once they are sorted in a fixed order, they will become the same. This code is much shorter (this idea can be done in just 1 line using Python as here). However, it takes much longer time — 76 ms in C++.

1
2
3
4
5
6
7
8
class Solution {
public:
bool isAnagram(string s, string t) {
sort(s.begin(), s.end());
sort(t.begin(), t.end());
return s == t;
}
};

https://discuss.leetcode.com/topic/20831/python-solutions-sort-and-dictionary

Python solutions (sort and dictionary).

1
2
3
4
5
6
7
def isAnagram1(self, s, t):
dic1, dic2 = {}, {}
for item in s:
dic1[item] = dic1.get(item, 0) + 1
for item in t:
dic2[item] = dic2.get(item, 0) + 1
return dic1 == dic2
1
2
3
4
5
6
7
def isAnagram2(self, s, t):
dic1, dic2 = [0]*26, [0]*26
for item in s:
dic1[ord(item)-ord('a')] += 1
for item in t:
dic2[ord(item)-ord('a')] += 1
return dic1 == dic2
1
2
def isAnagram3(self, s, t):
return sorted(s) == sorted(t)

https://discuss.leetcode.com/topic/23973/0ms-c-solution-o-n-time

0ms C++solution,O(n)time

1
2
3
4
5
6
7
8
9
10
11
bool isAnagram(string s, string t) {
int alp[26]={};
for (int i = 0; i < s.length(); i++)
alp[s.at(i) - 'a']++;
for (int i = 0; i < t.length(); i++)
alp[t.at(i) - 'a']--;
for (int i=0;i<26;i++)
if (alp[i] != 0)
return false;
return true;
}

https://discuss.leetcode.com/topic/20485/share-my-java-solution

Share my java solution

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
public class Solution {
public boolean isAnagram(String s, String t) {
if(s.length()!=t.length()){
return false;
}
int[] count = new int[26];
for(int i=0;i<s.length();i++){
count[s.charAt(i)-'a']++;
count[t.charAt(i)-'a']--;
}
for(int i:count){
if(i!=0){
return false;
}
}
return true;
}
}

https://discuss.leetcode.com/topic/20314/accepted-java-o-n-solution-in-5-lines

Accepted Java O(n) solution in 5 lines

The idea is simple. It creates a size 26 int arrays as buckets for each letter in alphabet. It increments the bucket value with String s and decrement with string t. So if they are anagrams, all buckets should remain with initial value which is zero. So just checking that and return

1
2
3
4
5
6
7
8
9
public class Solution {
public boolean isAnagram(String s, String t) {
int[] alphabet = new int[26];
for (int i = 0; i < s.length(); i++) alphabet[s.charAt(i) - 'a']++;
for (int i = 0; i < t.length(); i++) alphabet[t.charAt(i) - 'a']--;
for (int i : alphabet) if (i != 0) return false;
return true;
}
}
谢谢你,可爱的朋友。