# Determining if two strings are anagrams of each other

Is this code a good solution for the question, or is there a better way to do it?

package ArraysAndStrings;

import java.util.Arrays;

public class anagram{

private boolean isAnagram = false;

public boolean Anagrams(String str1, String str2){

if(str1.length() != str2.length()){
return isAnagram;
}

boolean [] char_set = new boolean[256];
boolean [] char_set1 = new boolean [256];

for(int i =0;i<str1.length();i++){

int val1 = str1.charAt(i);
int val2 = str2.charAt(i);

char_set[val1] = true;
char_set1[val2] = true;
}

if(Arrays.equals(char_set, char_set1)){
isAnagram = true;
}

return isAnagram;

}

public static void main(String [] args){

anagram ang = new anagram();

System.out.println(ang.Anagrams("mary","army"));

}

}

• The code is wrong: it says that "mmary" and "armyy" are anagrams.
– vnp
Jan 15 '16 at 19:30
• @vnp Given that the code includes a "test case", and that the author appears to be unaware of the bug, I would suggest that you write that as an answer. Jan 15 '16 at 19:31
• One (fairly) efficient way to do the job is to sort the characters in each string, then compare the results. The two are anagrams if and only if the results are equal. Jan 15 '16 at 19:32
• Please do not edit the code in your review. See what you may do. Jan 15 '16 at 20:30
• Your code crashing when it sees a codepoint > 255, so it only works for less than 1% of all allocated codepoints. Jan 16 '16 at 13:13

The code is technically broken: it only tells that the strings are composed of the same letters. It is not enough for the strings to be anagrams. Each letter must appear the same number of times in both strings.

Making your char_set array integer instead of boolean you can get the correct result still in linear time:

    int [] counters = new int[256];
set_counters_to_zero();
for (int i = 0; i < str1.len(); i++) {
counters[str1.charAt(i)]++;
}
for (int i = 0; i < str2.len(); i++) {
counters[str2.charAt(i)]--;
}
return all_counters_are_zero();

• @navindren Sorting is generally slower than linear time, and is usually O(n log n), where n is the number of elements to sort. Potentially a radix sort could be used here (though it is up to you to implement) to get the same linear asymptotic performance, but it will likely still be slower than this solution. Jan 15 '16 at 20:25
• @vpn set_counters_to_zero is unneeded in Java, counters automatically gets 0-initialized. Also a potential hazard is if I give you unicode characters... in such a case, to minimize memory usage I would advise making counters into Map<Character, Integer> Jan 15 '16 at 20:30
• I love the single-array approach, since you can then return false if any decrement goes below zero; in which case you can also return true after the second loop, and all_counters_are_zero() is unneeded. Whether checking every decrement against zero is any faster than just incrementing for all letters, decrementing for all letters, then comparing the sums of each all letter, is debatable, and would depend on what proportion of letters are likely to be 1) duplicated in each string, and 2) common between both strings. If either is low, I think checking each decrement becomes worthwhile. Jan 16 '16 at 2:25
• @DewiMorgan all_counters_are_zero is still necessary, for it is possible that all of them stay positive (unless I misread your proposal).
– vnp
Jan 16 '16 at 5:14
• @mleyfman Re zeroing: yes it is C++ism. Re unicode characters: you are absolutely correct. Yet I don't think we want OP to dive right in these complications.
– vnp
Jan 16 '16 at 5:16

### Class names in Java should begin with an uppercase letter

Naming this class anagram is against Java's standard naming convention. It should be:

public class Anagram {


### Member variables aren't meant to hold a method's return value

private boolean isAnagram = false;


Currently you're using isAnagram as a member variable, which means any method inside your class could modify it. This doesn't make much sense, since you should only want the method that checks for anagrams to control it. In fact, you might even consider getting rid of this altogether.

### Method names should begin with a lowercase letter

 public boolean Anagrams(String str1, String str2){


Again, to conform Java's naming convention, the Anagrams method should be called anagrams. But, your class is already called Anagram. Maybe, this method is better named as isAnagram(), since it is checking if two strings are anagrams.

### Algorithmic issues

As vnp pointed out in this answer, your original algorithm only considers if both strings have the same letters, not checking if those letters occur the same number of times. Is there a better way to check for an anagram?

What if we took each string, split it into an array of all of its letters, and sorted those arrays? We would have an anagram if those arrays were identical. You added a good implementation to your post, but it still needs improvement:

char [] c1 = new  char [str1.length()];
char [] c2 = new char [str2.length()];

Arrays.sort(c1);
Arrays.sort(c2);


You create c1 and c2 but never store anything in them! So, your algorithm will always return true when passed two strings of equal length, because it's really only comparing empty arrays.

Java already gives us String.toCharArray() which will take any String and produce a char[] from it, so use it, and you don't have to worry about manually creating the arrays:

char[] c1 = str1.toCharArray();
char[] c2 = str2.toCharArray();


Also, if you just return the value you're getting from Arrays.equals(), you won't have to keep the isAnagram variable around anymore.

Note that this algorithm is still incomplete for detecting anagrams, as detailed by this comment. Additional improvements can and probably should be added.

### Final version

public class Anagram {
public boolean isAnagram(String str1, String str2) {
if(str1.length() != str2.length()) {
return false;
}

char[] c1 = str1.toCharArray();
char[] c2 = str2.toCharArray();

Arrays.sort(c1);
Arrays.sort(c2);

return Arrays.equals(c1, c2);
}

public static void main(String[] args) {
Anagram anagram = new Anagram();
System.out.println(anagram.isAnagram("mary","army"));
}
}

• Rather than solely being upset about the senselessness of a member variable being exposed to other methods, you could also note that usage of a member variable provides other issues, like only being set when an instance of the class is created and later remembering the value it was last set to. Thus, if you first call with parameters 'mary' and 'army', it's set to true, then after that even a call with parameters 'three' and 'two' will return true. Jan 15 '16 at 22:37
• Since subject of an anagram could be a word or a phrase, I think spaces should not be considered. Plus the equality check should not be case-sensitive. Example: "Anna Madrigal" and "A man and a girl" are anagrams of each other. Jan 16 '16 at 7:18
• I think the method should be static. Just like main(...). Jan 16 '16 at 7:21
• Your final version is still buggy. Consider äo which is clearly not an anagram of öa, despite your code thinking so. Jan 16 '16 at 13:16
• @CodesInChaos - With your example, it returns false, as expected. Jan 16 '16 at 18:38

This version addresses some issues with accented characters and whitespace as mentioned in comments. E.g "\u006f\u0308\u0061", "\u0061\u0308\u006f" works as expected, as does "Anna Madrigal", "A man and a girl".

First step is to convey to lowercase and normalize the Unicode representation of accented characters to composed forms where possible. That normalization may not be correct in all situations. I'm not sure because I speak English and we don't use a lot of accented characters. An alternative to the normalization I've done is to normalize to decomposed form and then filter out any combining marks. Anyway, öa and äo are correctly not considered anagrams regardless of if the original encoding was decomposed or not using the method below.

We then get the sequence of characters, not including whitespace to account for cases such as "Anna Madrigal", "A man and a girl".

The comparison is done using the sorted arrays, because it is less code and optimization was not required in the question (premature optimization being evil and all), but to avoid the sorting overhead the histogram approach used in other answers can also be used after we have produced the filtered sequence of characters. The key is coming up with some canonical representation of each string and then checking if they are the same. Sorted characters or histogram work well for that.

public static boolean isAnagram(String str1, String str2) {
String s1 = Normalizer.normalize(str1.toLowerCase(), Normalizer.Form.NFC);
String s2 = Normalizer.normalize(str2.toLowerCase(), Normalizer.Form.NFC);

int[] cp1 = s1.chars().filter(cp -> !Character.isWhitespace(cp)).sorted().toArray();
int[] cp2 = s2.chars().filter(cp -> !Character.isWhitespace(cp)).sorted().toArray();

return Arrays.equals(cp1, cp2);
}