How to find out if two Strings are anagrams… When you first come across this problem you will probably think to yourself – easy, I know what an anagram is and I know how to find out if two Strings are anagrams… I can totally solve this problem! Just go through the first string and for every character check if it appears in the second one. Done. Now sure that would work… About the same way that flying north-east will eventually take you from Toronto to California… although it’ll take you a couple of days and you will probably have to go through North Korea at some point (Ouch!).
But is there a better way? Interviewers will most likely want you to prove you understand clearly if this can be improved and how. Well as a first step, let’s analyze the character by character checking method. I am not going to write code for that since it is pretty trivial (and it would look pretty horrible IMO :P), but instead let’s try to just lay down our algorithm for it and try to find what our bottlenecks are. Let’s see:
- Time Complexity: For each letter in the first String (n) you will go through each letter in the other String (*n) making your time O(n2). (Double Ouch! On a second thought, maybe it’s better to travel through North Korea.. Ok, ok, I am just messing with you!)
- Auxiliary Space Complexity: Just some temporary constant vars. O(1).
So on your venture to optimize the horrible algorithm from before, you will probably start thinking about optimizing the time complexity. Well we know that sorting takes only O(n*log(n)), (Check this out if you want to see more Sorting algorithm fun) so if we somehow applied it we could do much better. Let’s give it a try:
How to find out if two strings are anagrams – Java – Sorting
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 |
public class CustomStringUtil { /** * Writing out an anagram method is fun! * Usage example: anagram("foo", "bar") returns false, * anagram("fgoo","goof") returns true, * @param sFirst - first given String * @param sSecond - second given String * @return boolean value for whether the given strings are anagrams. */ boolean firstIsAnagram(String sFirst, String sSecond) { // let's try the sorting way char[] cFirstArray = sFirst.toCharArray(); char[] cSecondArray = sFirst.toCharArray(); Arrays.sort(cFirstArray); Arrays.sort(cSecondArray); return Arrays.equals(cFirstArray, cSecondArray); } } |
Let’s do a quick time/space complexity analysis. We have 3 operations done here sequentially:
- Copying a String to a char array: Time – O(n) (time it takes to set each element of the array); Space – O(n) (Space the array takes)
- Sorting an array: Time – O(n*log(n)) (you should know at least 1 algo which does this. If not, check MergeSort; Space – O(n) (we could optimize but we’ll leave it at that for now)
- Comparing two arrays: Time – O(n) (going through the arrays at the same time); Space – O(1) (maybe a temporary counter might be needed).
So to sum this up we finish our analysis by stating the time complexity of our new algorithm will be O(n*log(n))
Homework Question #1: What is the space complexity of this algorithm?
Good, you might think. But the interviewer at this point will probably ask you if you can further optimize the algorithm you have. And you start thinking: What do we know about characters that we might be able to use to our advantage?
Chars are a finite set! In fact let’s take a look at the ascii extended table:
We can use this to our leverage. We can create an array with all chars as indexes and count how many times it occurs in each String. Furthermore we can use only one array and increase the char count for the first String and decrease it for the second. The only case when the two Strings are anagrams is when the final array after increasing and decreasing will still have a count of 0. Meaning the amount of all specific chars in one array was equal to the amount of specific chars in the other. Anyway enough of this rant. Let’s try to put this in a clean step by step algorithm:
How to find out if two strings are anagrams – Algorithm
- Make an array of 256 ints, one per each possible char
- For each char in the first String, increase its int equivalent in the array by 1
- For each char in the second String, decrease its int equivalent in the array by 1
- If the array still has all 0s, then the Strings are anagrams!
Seems like we have it down in nice small trivial steps, so why not just get straight to coding!
How to find out if two strings are anagrams – Java – Cached Array
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 |
public class CustomStringUtil { /** * Writing out an anagram method is fun! * Usage example: anagram("doo", "bam") returns false, * anagram("gool","logo") returns true, * Assumes existence of only a finite set of 256 chars * @param sFirst - first given String * @param sSecond - second given String * @return boolean value for whether the given strings are anagrams. */ public static boolean secondIsAnagram(String sFirst, String sSecond) { if (sFirst.length() != sSecond.length()) { //Anagrams with different length? Never heard of such thing return false; } int[] asciiChars = new int[256]; // decreasing loop will make it so we only access sFirst.length() once :) for (int i = sFirst.length() - 1; i>=0; --i) { ++asciiChars[sFirst.charAt(i)]; } for (int i = sFirst.length() - 1; i>=0; --i) { char currChar = sSecond.charAt(i); if (asciiChars[currChar] == 0) { return false; } --asciiChars[currChar]; } return true; } } |
In this case we have the following analysis:
- Time Complexity – O(n) (time to go through the arrays at once)
- Space Complexity – O(1)
Homework Question #2: Why is the Auxiliary Space complexity O(1)? We are building an auxiliary array after all aren’t we?
Final thoughts: The above code makes one assumption – that we only have a finite set of 256 chars. (as is the case for ASCII extended set). Remember that assumptions are a huge pitfall in programming. So you should be very careful with them. State them clearly in your code.
I also put a small fun note to make the method about a billionth time faster :P, which is to use a decreasing for loop! (an increasing one would have resulted in more variables being created or length() accessed multiple times) This has no real-world use, so honestly… don’t try this at home :P. At this point, hopefully if you get asked this in an interview, you will easily build an implementation to find whether two strings are anagrams in Java.
Hope you guys enjoyed it… and I’ll see you guys next time ;D
Latest posts by Ajk (see all)
- Find Median from Numbers Array - January 1, 2018
- Find Whether a Number Can Be the Sum of Two Squares - August 12, 2017
- How to Find Two Primes Whose Sum is Equal to a Number N - April 22, 2017
n ordstrom
How to find out if two Strings are anagrams Java | FitCoding