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

CC150-1.3.java

// Ask the interviewer about details: are the characters case sensitive, 
// are the white space and special characters significant?

/**
 * Solution 1
 * Assume the string falls under a certain encoding. 
 * Check if the two strings have the same character count.
 * Use an extra constant
 * size array of integers to store the frequency of each character in str1,
 * for each character in str2, minus the frequency array's value by 1. In
 * the end, check if each element in the frequency array is 0, if not then
 * str1 is not a permutation of str2. Time complexity O(n), Space Comlexity O(1)
*/

public boolean permutation(String s1, String s2) {
	if (s1 == s2)
		return true;
	if(s1==null||s2==null)
		return false;
	int len1 = s1.length();
	int len2 = s2.length();
	if (len1 != len2)
		return false;
	//For basic ASCII size is 128, extended ASCII 256, UNICODE16 is 65536
	int[] freqs=new int[256];
	for(int i=0;i<len1;i++){
		freqs[s1.charAt(i)]++;
		freqs[s2.charAt(i)]--;
	}
	for(int i=0;i<256;i++){
		if(freqs[i]!=0)
			return false;
	}
	return true;
}
---------------------------------------
/**
* Solution 2: Sort the two string characters and then compare if the sorted strings are the same
* Takes O(nlgn) time and O(n) extra space. Not as good as the other solution
* 
*/

public boolean permutation(String s1, String s2) {
	if (s1 == s2)
		return true;
	if(s1==null||s2==null)
		return false;
	int len1 = s1.length();
	int len2 = s2.length();
	if (len1 != len2)
		return false;
	return sort(s1).equals(sort(s2));
	
}

private String sort(String s) {
	// TODO Auto-generated method stub
	char[] c=s.toCharArray();
	Arrays.sort(c);
	return new String(c);
}