Anagram Algorithm in Java solving if two strings are anagrams or not
This is the java solution for checking if the given two strings are anagrams or not. For the examples of anagrams and the approach I used and analysis of the code, see analysis of anagram algorithm
Find missing numbers from billion number lists with limited memory
Anagram algorithm in Java solution
package algorithm;
import java.util.Arrays;
/**
* Determine if the given two strings are anagrams or not
* A solution in java programming language
* @author https://gullele.com
*
* Analysis - this would run in o(nlogn) for the sorting part and all other others would be in o(n)
* Hence it is o(nlogn) + o(n) ==> o(nlogn) assuming worst case sorting.
*/
public class Anagram implements AnagramFinder {
public static void main(String string[]) {
String string1 = "Debit Card ";
String string2 = "bad credit";
AnagramFinder anagramFinder = new Anagram();
if (anagramFinder.areAnagrams(string1, string2)) {
System.out.println("Anagrams");
} else {
System.out.println("Not Anagrams");
}
}
public Anagram() {
}
@Override
/**
* Verify if the given words are anagrams or not
*/
public boolean areAnagrams(String s1, String s2) {
if (s1 == null || s2 == null) { //I don't think we would assume null is anagram at all..
return false;
}
//get rid of the spaces
s1 = s1.replaceAll("\\s+", "").toLowerCase();
s2 = s2.replaceAll("\\s+", "").toLowerCase();
//no need to proceed if the length is not the same. assumed the anagrams are the same in length
if (s1.length() != s2.length()) {
return false;
}
//then order the string in characters
char[] ordereds1 = sortChars(createCharArray(s1)); //o(nlogn)
char[] ordereds2 = sortChars(createCharArray(s2)); //o(nlogn)
//first thing first, if the size is not the same, then we are done
int index = 0;
while (index < ordereds1.length) { //this would run o(n)
if (ordereds1[index] != ordereds2[index]) {
return false;
}
index++;
}
return true;
}
/**
* Takes the string and converts it to characters
* @param string
* @return
*/
private char[] createCharArray(String string) {
return new char[string.length()];
}
/**
* if I have to implement it I can use quick sort and make it at least n(logn)
* @param chars
* @return array
*/
private char[] sortChars(char[] chars) {
Arrays.sort(chars);
return chars;
}
}
The above anagram algorithm solution is in java but it can be performed in any programming language.
Check if there are three numbers a, b, c giving a total T from array A
binary tree problems with solution
Kadane’s algorithm in C – Dynamic Programming