Permutation Check in Java

Here is a new Algorithm problem continuing our season. If you missed the first article, check it here: Decide if a String has duplicates.

Our next problem description is the following:

Check Permutation: Given two strings, write a method to decide if one is a permutation of the other.

Here, we should ask the following questions:

• Is the permutation comparison case sensitive?
  • That means: dog equal to Dog?
• We should ask if whitespace characters are significant?
• What is the character coding?

Our assumption is that our comparison is case sensitive, whitespaces are significant, and we use ASCII.

Solution #1

Think about the difference between two strings and whether they are the permutations of each other. The solution is simple: They have the same character count and only the character order differs.

If you find this statement, the task becomes quite straightforward.

We just need to compare the sorted versions of the strings.

        private static final String perm1 = "abcdefga";
private static final String perm2 = "abcdfega";


private String sort(String s) {

char[] content = s.toCharArray();
java.util.Arrays.sort(content);
return new String(content);
}

public Boolean getIsPermutations() {
if(perm1.length() != perm2.length()) return false;
return sort(perm1).equals(sort(perm2));
}

Although the above example is very clean and simple, performance is very important, so we may need to implement it in a different way.

Solution #2

We can implement an algorithm through the definition of "two words with the same character counts."

The below algorithm counts how many times each character appears, and then, it compares the two arrays.

boolean permutation(String s, String t) {
  if (s.length() != t.length()) {
    return false;
  }
  int[] letters = new int[128];// Assumption that it is in ASCII, you should always care about it.
  char[] s_array = s.toCharArray();
  for (char c : s_array) { // count number of each char in s.
    letters[c]++;
  }
  for (int i= 0; i < t.length(); i++) {
    int c = (int) t.charAt(i);
    letters[c]--;
    if (letters[c] < 0) {
      return false;
    }
  }
return true; 
}

Notes

Hope you enjoyed my latest programming puzzle. I recommend you to try to solve them before going through the solution.

And feel free to share your ideas in the comments below.

This problem is from the Cracking the Coding Interview book, which I wrote about under the Resources menu.