Check Permutation

出处

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

Detail: if white space is significant

Solution

可以排序或者用 hashtable 来做

Complexity

排序的时间复杂度是 O(nlogn)，空间复杂度 O(1)，hashtable 时间复杂度 O(n)，空间复杂度 O(n)

Code

public static boolean isPermutationHashTable(String str1, String str2){
    // check special case first
    if (str1 == null && str2 != null || str1 != null && str2 == null){
        return false;
    }
    if (str1.length() != str2.length()){
        return false;
    }

    int[] alphabet = new int[256];
    for (int i = 0; i < str1.length(); i++){
        alphabet[str1.charAt(i)]++;
    }

    for (int i = 0; i < str2.length(); i++){
        alphabet[str2.charAt(i)]--;
        if (alphabet[str2.charAt(i)] < 0){
            return false;
        }
    }
    return true;
}

public static boolean isPermutationSort(String str1, String str2){
    // check special case first
    if (str1 == null && str2 != null || str1 != null && str2 == null){
        return false;
    }
    if (str1.length() != str2.length()){
        return false;
    }

    char[] str1char = str1.toCharArray();
    char[] str2char = str2.toCharArray();
    Arrays.sort(str1char);
    Arrays.sort(str2char);

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