This content originally appeared on Level Up Coding - Medium and was authored by Thenjiwe kubheka
This is a famous interview question, loved by many Big Tech companies. With this problem, you basically need to write a program that checks if two strings are anagrams of each other.
What is an Anagram you may ask? An anagram is a word or phrase which can be can be formed by rearranging the letters of the other word or phrase!
Example: “New York Times” can be rearranged to form “monkeys write”
So we are not adding or removing anything just, rearranging the letters, it is a fun game for nerds.
Let's write a function that checks if string 2(“monkeys write”) is an anagram of string 1( “New York Times”). Let's do some string processing before we proceed.
We want to get rid of spaces and capital letters, Python counts spaces as characters. We will name string 1(S1) and string 2(S2).
s1 = s1.replace(" ","").lower
s2 = s2.replace(" ","").lowerWe have done our string processing, and have gotten rid of our spaces and every character in our string is lower case.
We can resume with our problem solving.
Method 1: Using the Sorted Built In Function
The first method is cheating the system a bit, by using the built in Python method of sorted. This is not appropriate for the Technical interviews, but is worth mentioning.
print(sorted(s1)== sorted(s2))
This a very simple solution, but not very efficient as comparison based sorting algorithms will take O(nlogn) at best case. So we need to think a bit further.
Method 2: Using An Additional Data Structure
We will use the dictionary data structure to keep track of letters we have come across. So we start with string1, we check for the n, we should also have an n in string two.
Next we will evaluate e in string 1, which corresponds to e in string two, same applies to w. So with string1 we add the characters of our string to the dictionary. and with string 2, we remove characters of our from our dictionary, we populate and depopulate the dictionary and we must end up with zero elements.
lets create our function, which will take in string 1 and string 2.
def isAnagram(s1,s2)
Then we need to tell, the Python interpreter, to reserve a space in memory for us as we want to create a dictionary. We will name it tracker.
tracker = {}Now lets eliminate the first condition, make sure the length of both strings are equal. If they are not, then they possibly cannot be anagrams of each other. This would mean one string has extra characters or the other has less characters.
if len(s1) != len(s2):
return False
So if the two strings have the same length, then we can proceed. We start by looping through, the first string(s1).
for i in s1:
if i in tracker:
tracker[i] += 1
The above code is telling the interpreter, to loop through the first string. If i(a character) is in tracker(our dictionary). Then we increment the position of i by one, so we move to the next character.
If not then we initialize our count to 1. When we see a character for the first time, example N as it is the first character in “New York Times” we initialize it to 1. And if N would repeat itself within string1 then we increment it by 1.
We move to string 2 and do the same;
for i in s2:
if i in tracker:
tracker[i] -= 1
else:
tracker[i] = 1
so once we are done looping our dictionary, populating and depopulating it, our dictionary should be empty and we should have 0. If the dictionary does not equate to zero, then the strings are not anagrams of each other.
for i in tracker:
if tracker[i] != 0:
return False
So is it is equal to zero, then both strings are anagrams of each other. You can print the anagram.
print(isAnagram(s1,s2))
Additional Material
Thenjiwe Kubheka on LinkedIn: #algorithms #work #computerscience
Check If Two Strings Are Anagrams. was originally published in Level Up Coding on Medium, where people are continuing the conversation by highlighting and responding to this story.
This content originally appeared on Level Up Coding - Medium and was authored by Thenjiwe kubheka
Thenjiwe kubheka | Sciencx (2021-09-23T17:10:11+00:00) Check If Two Strings Are Anagrams.. Retrieved from https://www.scien.cx/2021/09/23/check-if-two-strings-are-anagrams/
Please log in to upload a file.
There are no updates yet.
Click the Upload button above to add an update.