Quite often interviewers just give a coding question to solve some of the standard questions. Finding out String Anagrams is one among them which gets covered by lot many and at different level interview positions.
Popular Java Coding Interview Questions – Finding out if two String are Anagrams
In my last post I started discussing about the Java Programming Interview questions and found the solution for a popular one: ‘How to find out Armstrong Numbers’ and provided the source code as well.
In continuation to that, today I am going to discuss about another quite common, tricky but a simple coding interview question:
Find out if two given strings are anagrams or not.
In addition to that, we will also have a look at a recursive method used to generate all the permutations of a given string. This at times, can be further implemented to validate the generated words in a dictionary, if provided.
Coming to the simple definition first: “An anagram is a word, name or phrase formed by rearranging the letters of another, using each original letter only once.” You can think of it like taking one word and then just scrambling the letters to get another word.
Some examples of valid and interesting anagrams:
Example of words which are NOT anagrams:
So now we are going to perform two tasks here with the help of Java code:
Task 1 has been achieved very simply by accepting two strings as inputs which may have multiple words even. Then removing all the spaces in between them and making the char array. Both the char arrays are then getting sorted and compared to find if equal or not.
Task 2 has been again coded simply but may be tricky to understand as it is using the recursive method calls.
To understand how it works, just take a three letters word ‘Red’.
Now, if you have to generate the different words using the three letters R, E, D, you would just shuffle them around and form the new words.
Now lets say we have five letters word, how will you approach now? You would most probably fix the position of first three letters and shuffle around rest two. Once done, you would fix the position of first two letters and shuffle rest. And at last, you would fix the first letter and shuffle rest.
Once all the words are formed this way, you would like to replace the position of first second and third letter and repeat the entire process. In short, each time you would fix a different letter in the beginning and then make all the possible shuffles.
The very same approach has been followed by the recursive method createAllPermutations. It is fixing the initial letter(s) and then making different combinations out of left out letters in the string.