Check if two strings are permutations of one another

Question

I am working my way through "Cracking the coding interview" problems and have finished implementing this question: "Given, two strings, write a method to decide if one is a permutation of the other". Can anyone give me any feedback on my implementation in regards of efficiency or improvements?

public static boolean containsPremutation(String firstString, String secondString){
 //Checking if either string is empty.
 if(firstString.isEmpty() || secondString.isEmpty())
 return false;
 //Checking if one string is larger than the other.
 if(firstString.length() > secondString.length() || secondString.length() > firstString.length())
 return false;
 //First convert the Strings into char[]
 char [] charFirstString = firstString.toCharArray();
 char [] charSecondString = secondString.toCharArray();
 //Secondly, aplhabetize/sort the char arrays
 Arrays.sort(charFirstString);
 Arrays.sort(charSecondString);
 //Thirdly, create new Strings out of the sorted char arrays
 String alphaFirstString = new String(charFirstString);
 String alphaSecondString = new String(charSecondString);
 //Now you can begin comparing each char in the Strings.
 // Begin iterating at the same char and if they are not the same char return false
 //otherwise continue iterating.
 for (int i = 0; i < alphaFirstString.length(); i++){
 if(alphaFirstString.charAt(i) != alphaSecondString.charAt(i))
 return false;
 }
 return true;

• Phrancis: Welcome to Code Review! Just so you know, the correct spelling is "permutation", not "premutation", I've made the correction in the question, but you may want to correct your code. Hope you get some good answers!
• rossmcm: Your test to see if one string is longer than the other could be simplified to if (firstString.length() != secondString.length() return false;
• Zhe: Why not just compare the arrays directly instead of converting to string again?
• TheLearner: @rossmcm thank you for your feedback! I agree with your comment. Thank you!!
• TheLearner: @Zhe I did not think about that, good point. I will attempt to fix my code with your suggestion. Thank you.

Answer 1

This question has used the word "permutation" for two strings, and in standard English what that's asking for is "is one the anagram of the other"? Using "anagram" as a search would help you find a lot of other information on this problem, especially on Code Review.

Your solution is significantly over-engineered. You have broken down the problem in to too many steps, and you've missed an opportunity to show how you would avoid code duplication.

Let's break down your code in to its stages:

1. Check each string is valid input
2. Check the strings are the same length
3. Extract the characters from each string
4. Sort each string's characters
5. Create a new String from each input's sorted characters.
6. Iterate over each of the sorted string's characters and compare to the other string.
7. Return the match status

Now, let's strip out the redundant parts... for example, you don't need to convert the sorted characters back to a string only to loop over each character again.... get rid of stage 5 and convert stage 6 to operate over the sorted array.

Also, stage 1, that's a bug. Two empty strings are anagrams of each other... agreed? Get rid of that check.

Now, what's left is two identical operations performed on two different inputs, which are then compared, so extract the common logic in to a function (Code reuse is a good thing):

private static final char[] sortedChars(String input) {
 char [] chars = input.toCharArray();
 Arrays.sort(chars);
 return chars;
}

Then, your code looks like:

public static boolean containsPremutation(String firstString, String secondString){
 char[] firstChars = sortedChars(firstString);
 char[] secondChars = sortedChars(secondString);
 ....
}

Now what? Instead of converting them to strings, we can use the core library's Arrays class to do the comparisons for us:

return Arrays.equals(firstSorted, secondSorted);

The full code would be:

private static final char[] sortedChars(String input) {
 char [] chars = input.toCharArray();
 Arrays.sort(chars);
 return chars;
}
public static boolean containsPremutation(String firstString, String secondString){
 char[] firstChars = sortedChars(firstString);
 char[] secondChars = sortedChars(secondString);
 return Arrays.equals(firstSorted, secondSorted);
}

Looking at the code that way, you can see other issues too...

• generally, "Hungarian Notation" is frowned on in Java Code Style - don't have String appended to variable names like firstString and secondString ... we know that they are strings.

• do we even need the variables in the contains... method? Could it just be:

  public static boolean containsPremutation(String first, String second){
   return Arrays.equals(sortedChars(first), sortedChars(second));
  }
  

• As mentioned in a comment, it's Permutation and not Premutation.

• TheLearner: Thank you for this feedback, I have replaced "firstString" and "secondString" to "firstWord" and "secondWord". Thank you for showing another implementation without the redundancy. I see that this code has fewer lines and steps. Is the time complexity any better?
• pzp: @TheLearner They have the same big-O complexity, but in practice, rolfl's answer is probably faster.

Answer 2

Even though rolfl already gave a great review, let me also mention some minor points:

• It's good practice to always put braces around blocks. This prevents simple bugs introduced by trying to amend the single-line block and forgetting the braces
• Checking for "different length" is easier with if (firstString.length() != secondString.length())
• You're overcommenting. A lot of these comments can be made or already are redundant through proper naming.
• Your placement of spaces is somewhat interesting:
  • In java usually the array indicators are placed directly adjacent to the type (char[] over char []).
  • An opening parenthesis for if, for, while and other block scopes is usually placed with one space distance. You're not consistent in how you do it. If statements don't get space, but for-loops do (if( vs for ()

• TheLearner: I have heard that braces could be excluded if the function is a one-liner, but did not know bugs could also be introduced. In terms of the spacing, you are right I have just gotten used to typing "char [] ". I am not sure what you mean by your last bullet point, are you saying I should always have a new line after using a loop? Thank you for your feedback!

Answer 3

 //Checking if either string is empty.
 if(firstString.isEmpty() || secondString.isEmpty())
 return false;

This doesn't seem right. Now if you have two empty strings, they are not permutations of each other. Why?

All other cases caught by this code would be caught by

 //Checking if one string is larger than the other.
 if(firstString.length() > secondString.length() || secondString.length() > firstString.length())
 return false;

Which might more briefly be written

 if (firstString.length() != secondString.length()) {
 return false;
 }

If one of the strings is empty and the other isn't, it will fail this check.

 //Thirdly, create new Strings out of the sorted char arrays
 String alphaFirstString = new String(charFirstString);
 String alphaSecondString = new String(charSecondString);
 //Now you can begin comparing each char in the Strings.
 // Begin iterating at the same char and if they are not the same char return false
 //otherwise continue iterating.
 for (int i = 0; i < alphaFirstString.length(); i++){
 if(alphaFirstString.charAt(i) != alphaSecondString.charAt(i))
 return false;
 }
 return true;

This seems overly complicated. Consider either

 for (int i = 0; i < alphaFirstString.length(); i++){
 if (charFirstString[i] != charSecondString[i]) {
 return false;
 }
 }
 return true;

or

 String alphaFirstString = new String(charFirstString);
 String alphaSecondString = new String(charSecondString);
 return alphaFirstString.equals(alphaSecondString);

Turning a perfectly handy random access array into a String just to process them letter by letter is a waste of time. Letter by letter processing is easier with the arrays. Or use the built-in for the strings. Or use @rolfl's suggestion of Arrays.equals, which worries about these fiddly problems for you.

Now, the time complexity here is going to be dominated by the sort. If you want to improve, you need to stop sorting. The alternative solution here is instead of sorting, to count the letters in the first word and then the second word.

 int[] counts = new int[CHARSET_SIZE];
 for (char letter : firstString.toCharArray()) {
 counts[letter]++;
 }
 for (char letter : secondString.toCharArray()) {
 counts[letter]--;
 }
 for (int count : counts) {
 if (count != 0) {
 return false;
 }
 }
 return true;

This would be linear in the sum of the string sizes and the size of the character set.

I haven't tested this, so you might have to cast letter to int to get this to work.

Answer 4

Everyone's answers have covered almost every comment I would have, I just would add a null check at the beginning to avoid NPE.

if (first == null || second == null) {
 throw new Exception("first and second cannot be null");
}