Valid Anagram
Statement
Given two strings s1 and s2, find whether s1 is an anagram of s2.
An anagram is a word or phrase created by rearranging the characters of another word or phrase while utilizing each of the original characters exactly once.
Constraints
- 1 ≤
s1.length(),s2.length()≤ 10³ s1ands2contain lowercase English characters
Solution
"""
production algorithm
"""
from collections import Counter
class Solution:
def is_anagram(self, str1, str2):
"""
time complexity O(n)
space complexity O(1)
"""
counter1, counter2 = Counter(str1), Counter(str2)
for character in counter1:
if not counter1.get(character) == counter2.get(character):
return False
for character in counter2:
if not counter2.get(character) == counter1.get(character):
return False
return True"""
unit tests
"""
from unittest import TestCase
from algorithms.counters.valid_anagram.solution import Solution
class SolutionTestCase(TestCase):
def test_character_mismatch(self):
# Given
string1 = "xmtdkjswqblefinxgcvp"
string2 = "ymtdkjswqblefinxgcvp"
solution = Solution()
# When
actual = solution.is_anagram(string1, string2)
# Then
expected = False
self.assertEqual(actual, expected)
def test_character_frequency_mismatch(self):
# Given
string1 = "xmtdkjswqblefinxgcvp"
string2 = "mmtdkjswqblefinxgcvp"
solution = Solution()
# When
actual = solution.is_anagram(string1, string2)
# Then
expected = False
self.assertEqual(actual, expected)
def test_is_anagram_frequency(self):
# Given
string1 = "xmtdkjswqblefinxgcvp"
string2 = "xmtdkjswqblefinxgcvp"
solution = Solution()
# When
actual = solution.is_anagram(string1, string2)
# Then
expected = True
self.assertEqual(actual, expected)Strategy
Counters.
Explanation
First, the algorithm counts the frequency of characters in the first and second string. Then, the unique characters of the counter of the first string are iterated. For all unique characters, if the character doesn’t exist in the counter of the second string, or the frequencies of the character in the first and second counter aren’t equal, then the two strings aren’t an anagram of each other. Afterwards, the same iteration is repeated for the unique characters of the counter of the second string. If both iterations complete, then the two strings are anagrams of each other.
Time Complexity
First, to count the frequency of characters in the first and second string, all characters of the first and second string are iterated. The time complexity to do so is O(n), where n is the total number of characters.
Then, the unique characters of both counters are iterated. At most, there are 26 unique characters in each counter, since the characters of the input strings are lowercase English characters. The time complexity to count the unique characters of both counters is O(1).
Therefore, the time complexity of the algorithm is O(n).
Space Complexity
At most, the size of each counter of the unique characters of the first and second string is 26. In other words, the auxiliary space of both counters is constant. Therefore, the auxiliary space complexity of the algorithm is O(1).
