CC-14 : Check if input String is an anagram.

Description:

Anagram of a word is another word formed using the same characters as the original word. Note that the frequency of each character in the newly formed word should be same as the frequency of the character in the original word. Given two input Strings check if they are anagrams.

Test cases and expected outputs:

Input Parameters	Expected outputs
The original strings are: listen, silent.	Sorted Str1 tsnlie Sorted Str2 tsnlie The input string are anagrams.
The original strings are: note, tonn.	Sorted Str1 tone Sorted Str2 tonn The input string are not anagrams.

Pseudocode:

checkAnagrams(str1, str2):

Call quicksort() method to sort characters of str1.

Call quicksort() method to sort characters of str2.

Iterate through str1 using for loop with idx as iteration variable and values of idx ranging from 0 to str1.length-1:

If st1.charAt(idx) !=str2.charAt(idx), then the input Strings are not anagrams, so return false.

If no mismatch found above, return true.

QuickSort(chars[], startIdx, endIdx):

char array named chars, start index startIdx and end index endIdx of chars are received as input parameters.

If (startIdx < endIdx) then execute following steps:

Initialize and integer variable pivot with value chars[endIdx]. We will use this variable to partition the elements into two partitions.

Initialize and integer variable iidx with value startIdx-1. We will use this variable to track and swap elements less than pivot to partition containing elemnts lesser than the pivot.

Iterate through chars using for loop with jidx as iteration variable and values of iidx ranging from startIdx to endIdx-1:

 If chars[jidx]<=pivot alphabetically, then:

Increment iidx by 1.

Swap elements at position iidx and jidx.

Swap elements at index iidx+1 and endIdx.

Set integer variable partitionIdx to iidx+1.

Call method quicksort(chars, startIdx, partitionIdx-1) to sort the partition with lesser elements than pivot element.

Call method quicksort(chars, partitionIdx+1, endIdx,) to sort the partition with greater elements than pivot element.

The element of chars array have been sorted now using Quick Sort, so return chars array from the method.

Code:

public boolean checkAnagram(String str1, String str2) {
	if (str1.length() != str2.length()) {return false;}
	str1=new String(quickSort(str1.toCharArray(),0, str1.length()-1));
	str2=new String(quickSort(str2.toCharArray(),0, str2.length()-1));
	System.out.println("Sorted Str1 "+str1);
	System.out.println("Sorted Str2 "+str2);
	for (int idx=0; idx < str1.length(); idx++) {
		if (str1.charAt(idx)!=str2.charAt(idx)) {
			return false;
		}
	}
	return true;
}


public char[] quickSort(char[] chars,int startIdx, int endIdx) {
	if(startIdx < endIdx) {
		char pivot=chars[endIdx];
		int iidx=startIdx-1;
		for (int jidx=startIdx; jidx < endIdx;jidx++) {
			if (Character.valueOf(chars[jidx]).compareTo(Character.valueOf(pivot))>0) {
				iidx++;		
				char swap=chars[iidx];
				chars[iidx]=chars[jidx];
				chars[jidx]=swap;
			}
		}
		char swap=chars[iidx+1];
		chars[iidx+1]=chars[endIdx];
		chars[endIdx]=swap;
		
		int partitionIdx=iidx+1;
		quickSort(chars, startIdx, partitionIdx-1);
		quickSort(chars, partitionIdx+1,endIdx);
	}
	return chars;
}

Click here to download and run code and test cases !

Below fully running code can be copied and run on Eclipse or other Java IDEs. Refer the classname in code below. If the class name below is "A", save the code below to a file named A.java before running it. Be sure to try your own test cases to enhance your understanding ! You can also tweak the code to optimize or add enhancements and custom features.

public class SortCheckIfAnagram {
 
public boolean checkAnagram(String str1, String str2) {
	if (str1.length() != str2.length()) {return false;}
	str1=new String(quickSort(str1.toCharArray(),0, str1.length()-1));
	str2=new String(quickSort(str2.toCharArray(),0, str2.length()-1));
	System.out.println("Sorted Str1 "+str1);
	System.out.println("Sorted Str2 "+str2);
	for (int idx=0; idx<str1.length(); idx++) {
		if (str1.charAt(idx)!=str2.charAt(idx)) {
			return false;
		}
	}
	return true;
}


public char[] quickSort(char[] chars,int startIdx, int endIdx) {
	if(startIdx < endIdx) {
		char pivot=chars[endIdx];
		int iidx=startIdx-1;
		for (int jidx=startIdx; jidx < endIdx;jidx++) {
			if (Character.valueOf(chars[jidx]).compareTo(Character.valueOf(pivot))>0) {
				iidx++;		
				char swap=chars[iidx];
				chars[iidx]=chars[jidx];
				chars[jidx]=swap;
			}
		}
		char swap=chars[iidx+1];
		chars[iidx+1]=chars[endIdx];
		chars[endIdx]=swap;
		
		int partitionIdx=iidx+1;
		quickSort(chars, startIdx, partitionIdx-1);
		quickSort(chars, partitionIdx+1,endIdx);
	}
	return chars;
}


public static void main(String[] args) {
	/***********************
	 Test cases given below:
	 **********************/
	boolean retVal;
	try {
	SortCheckIfAnagram sort=new SortCheckIfAnagram();
	String str1="listen";
	String str2="silent";
	System.out.println("\n\nThe original strings are: "+str1+" "+str2);
	retVal=sort.checkAnagram(str1,str2);
	if (retVal==true) {
		System.out.println("The input string are anagrams.");
	}else {
		System.out.println("The input string are *not* anagrams.");
	}
	
	
	str1="secure";
	str2="rescue";
	System.out.println("\n\nThe original strings are: "+str1+" "+str2);
	retVal=sort.checkAnagram(str1,str2);
	if (retVal==true) {
		System.out.println("The input string are anagrams.");
	}else {
		System.out.println("The input string are *not* anagrams.");
	}
	
	
	str1="note";
	str2="tonn";
	System.out.println("\n\nThe original strings are: "+str1+" "+str2);
	retVal=sort.checkAnagram(str1,str2);
	if (retVal==true) {
		System.out.println("The input string are anagrams.");
	}else {
		System.out.println("The input string are *not* anagrams.");
	}
	
	
			
	}catch (Exception exception) {
		System.out.print("Exception: "+ exception);
		exception.printStackTrace();
	}
		
}
}