An anagram is a rearrangement of letters to form another word. Example: "rat" and "tar" are anagrams.
Leetcode link: https://leetcode.com/problems/valid-anagram/
Given two strings s and t , write a function to determine if t is an anagram of s.
We assume the string contains only lowercase alphabets.
We can simply convert the string of characters into a list of characters and sort them. Doing so will mean that if the 2 words are actually anagrams, then the list will be exactly the same.
To calculate the time complexity, we analyse the internal operation of our methods.
list method which converts our string into a list of characters, will take a total of
sort method will take
O(nlogn) time. Python internally uses a modified Timsort. So overall, we have
O(n) + O(n) + O(nlogn) + O(nlogn) time complexity.
Overall, it simplifies to
O(nlogn) time complexity.
Useful link for time complexity of common Python methods: https://wiki.python.org/moin/TimeComplexity
O(n) space to store the characters in lists, where n refers to the length of the string.
Another way we can approach the problem is to count the number of times each character appears in the strings. We can do so using a dictionary.
Implementation is omitted as its straightforward:
- Put all characters of each string into 2 different dictionaries
- Iterate over the characters in each dictionary and check if the count of the character is the same