Code Challenge: Check Permutation - Java edition

#java #algorithms #codenewbie #programming

Today's problem is a fun one.

Problem

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

Solution 1

Clarifying questions are: Does white space count? Is the comparison case sensitive? Is the string in ASCI (I explain ASCI in this post)? Once you have determined these answers, you can move on to solve the problem.

If the two strings are permutations we know they should have the same length. So one of the first things we can do is check if the strings are different lengths. We also know that permutations are the same characters but in a different order. If we sort the strings, we can simply compare the two strings.

// Sort the string
public static String sort(String a) {
    char[] c = a.toCharArray();
    Arrays.sort(c);
    return new String(c);
}

public static boolean checkPermutation(String a, String b) {
    // permutations should be equal length
    if (a.length() != b.length() ) {
       return false;
     }

     return sort(a).equals(sort(b));
}

This solution is clean and readable and easy to understand. The Time Complexity is O(nlogn) since Java's Arrays.sort uses a Quicksort when sorting primitives.

Solution 2

This solution is faster but less clear. We use an array data structure to store counts of all possible characters (assuming ASCI). We loop through the first string to load the counts of the numbers, then loop through the second string to decrement the counts of each character. We know that if that count falls below zero, a character doesn't match.

public static boolean checkPermutations(String a, String b) {
    if (a.length() != b.length()) {
        return false;
    }

    int[] letters = new int[128]; // assuming ASCI
    for (int i = 0; i < a.length(); i++){
        // for each position of ASCI length(128) keep a count of the characters.
        letters[a.charAt(i)]++;
    }
    for (int i = 0; i < b.length(); i++) {
        // find the position in our ASCI array and subtract 1
        letters[b.charAt(i)]--;
        // if it's less than zero, we can return false
        if (letters[b.charAt(i)] < 0) {
            return false;
        }
    }
    return true;
}