I have a program that shows you whether two words are anagrams of one another. There are a few examples that will not work properly and I would appreciate any help, although if it were not advanced that would be great, as I am a 1st year programmer. "schoolmaster" and "theclassroom" are anagrams of one another, however when I change "theclassroom" to "theclafsroom" it still says they are anagrams, what am I doing wrong?
import java.util.ArrayList;
public class AnagramCheck
{
public static void main(String args[])
{
String phrase1 = "tbeclassroom";
phrase1 = (phrase1.toLowerCase()).trim();
char[] phrase1Arr = phrase1.toCharArray();
String phrase2 = "schoolmaster";
phrase2 = (phrase2.toLowerCase()).trim();
ArrayList<Character> phrase2ArrList = convertStringToArraylist(phrase2);
if (phrase1.length() != phrase2.length())
{
System.out.print("There is no anagram present.");
}
else
{
boolean isFound = true;
for (int i=0; i<phrase1Arr.length; i++)
{
for(int j = 0; j < phrase2ArrList.size(); j++)
{
if(phrase1Arr[i] == phrase2ArrList.get(j))
{
System.out.print("There is a common element.\n");
isFound = ;
phrase2ArrList.remove(j);
}
}
if(isFound == false)
{
System.out.print("There are no anagrams present.");
return;
}
}
System.out.printf("%s is an anagram of %s", phrase1, phrase2);
}
}
public static ArrayList<Character> convertStringToArraylist(String str) {
ArrayList<Character> charList = new ArrayList<Character>();
for(int i = 0; i<str.length();i++){
charList.add(str.charAt(i));
}
return charList;
}
}
Works perfectly! But not a good approach because it runs in O(n^2)
If you sort either array, the solution becomes O(n log n). but if you use a hashmap, it's O(n). tested and working.
By using more memory (an HashMap of at most N/2 elements)we do not need to sort the strings.
This function is actually running in O(N) ... instead of O(NlogN) for the solution that sorts the strings. If I were to assume that you are going to use only alphabetic characters I could only use an array of 26 ints (from a to z without accents or decorations) instead of the hashmap.
If we define that : N = |one| + |two| we do one iteration over N (once over one to increment the counters, and once to decrement them over two). Then to check the totals we iterate over at mose N/2.
The other algorithms described have one advantage: they do not use extra memory assuming that Arrays.sort uses inplace versions of QuickSort or merge sort. But since we are talking about anagrams I will assume that we are talking about human languages, thus words should not be long enough to give memory issues.
Thanks for pointing out to make comment, while making comment I found that there was incorrect logic. I corrected the logic and added comment for each piece of code.
You should use something like that:
Default value for
isFound
should be false. Just it