2
\$\begingroup\$

I have written this code and I am wondering if the code could be optimised.Please review.

 public class Anagram1{
   public static boolean check(char[] c1,char[] c2,int l1,int l2){

     /*if the lengths of the strings are not equal,they cannot be anagrams of each other */

    if(l1!=l2){
        return false;
    }

    int count = 0;

    //nested for loops to compare the characters of both strings.
    //if the characters match,then the strings are anagrams of each other.
    for(int i=0; i<l1; i++){
        for(int j=0; j<l2; j++){
            if(c1[i]==c2[j]){
                count++;
                break;      //"break" used so as to count only a single occurrence of a
            }               //character.
        }
    }
    if(count==l1 && count==l2){
        return true;
    }
    return false;
}

public static void main(String[] args) {

    String s1 = "abcd";

    String s2 = "acdb";

    char[] c1 = s1.toCharArray();

    char[] c2 = s2.toCharArray();

    int l1 = s1.length();

    int l2 = s2.length();

    System.out.println(check(c1,c2,l1,l2));
  }
}
\$\endgroup\$
4
  • \$\begingroup\$ Most answers seem to only look for anagrams in words. In your scenario, are you looking to check if phrases are anagrams of each other? Consider the following: "Anagram" and "Nag a ram" (Thanks Google) \$\endgroup\$
    – Yousend
    Nov 7 '16 at 19:27
  • 1
    \$\begingroup\$ don't use old-school for-int loops. use the fast enumeration Java has. It looks better, removes a useless variable, and in some cases takes care of things like concurrency checks. \$\endgroup\$
    – njzk2
    Nov 7 '16 at 21:47
  • \$\begingroup\$ @akadian - I don't think that I have to check for that condition unless otherwise specified because, in the language of computer,both the strings are conspicuously different. \$\endgroup\$ Nov 17 '16 at 19:28
  • \$\begingroup\$ @MayankGupta I know that they are different in strings, my comment was mainly referring to the definition of an anagram. It doesn't add much, but just figured you might want to specify on your definition. Anagram: "...the result of rearranging the letters of a word or phrase to produce a new word or phrase..." It's your program, so it's really up to you, but otherwise you just need to ignore white space from your input strings to compare. \$\endgroup\$
    – Yousend
    Nov 17 '16 at 19:38
5
\$\begingroup\$

About the algorithm (ITS NOT CORRECT). I will still review it for you:

  • Passing l1 and l2 in boolean check(char[] c1,char[] c2,int l1,int l2) as argument is redundant. You can use the inherent c1.length and c2.length provided by Java.
  • if(count==l1 && count==l2) Any one check would do as you overruled l1!=l2 very early. Remember?

  • Failure cases: "aab" and "abb" both would be called anagrams. Hope you discover that.

About the algorithm:

  • There are simpler better ways to check if two strings are anagram. How? Sort the strings and compare character by character. Not impressed? Do a character count using a Map for each character and compare it for other array. And there are many more. Happy Googling.
\$\endgroup\$
2
  • \$\begingroup\$ I believe he used the word anagram instead of palindrome. \$\endgroup\$ Nov 7 '16 at 16:46
  • \$\begingroup\$ My bad :) Updated the comments. \$\endgroup\$
    – thepace
    Nov 7 '16 at 16:48
3
\$\begingroup\$

Your solution doesn't exactly work. For example, if you use:

String s1 = "abbd";
String s2 = "acdb";

You will find that it returns true even though each character in s2 does not appear in s1.

See my solution below which will work for any two strings to ensure they are anagrams.

import java.util.ArrayList;
import java.util.Collections;

public class Anagram1 {
    public static void main(String[] args) {
        String s1 = "abcd";
        String s2 = "adbc";
        System.out.println(check(s1, s2));
    }

    public static boolean check(String s1, String s2) {
        // Remove white space and change to lower case.
        s1 = s1.replace(" ","").toLowerCase();
        s2 = s2.replace(" ","").toLowerCase();

        // If they are equal, return true. If they are not the same length,
        // return false.
        if (s1.equals(s2)) {
            return true;
        } else if (s1.length() != s2.length()) {
            return false;
        }

        // Convert to ArrayList for sorting.
        ArrayList<Character> sl1 = new ArrayList<Character>();
        ArrayList<Character> sl2 = new ArrayList<Character>();

        for (char ch1 : s1.toCharArray()) {
            sl1.add(ch1);
        }

        for (char ch2 : s2.toCharArray()) {
            sl2.add(ch2);
        }

        // Sort both ArrayLists
        Collections.sort(sl1);
        Collections.sort(sl2);

        // If they are equal return true, else return false.
        if (sl1.equals(sl2)) {
            return true;
        } else {
            return false;
        }
    }
}

In this example, I use two ArrayLists (one for each String) to sort them into alphabetical order and then compare the results to see if they are equal. This solution takes into account repeating characters and it ensures that both String's include all the characters (not just checking one against the other).

EDIT: Thanks to @Akadian for pointing out the case where a phrase is passed in, to address this you can use the replace method for the String class to remove any whitespaces, also in case the phrase is capitalised you would need to call toLowerCase() to ignore the case of specific letters.

\$\endgroup\$
3
  • \$\begingroup\$ Hi Adam, I think we should avoid providing solutions here. Instead hint at the issue and solution. Let the thirsty find the water with little pebbles you provide :) \$\endgroup\$
    – thepace
    Nov 7 '16 at 16:47
  • \$\begingroup\$ If OP includes phrases in his definiton of anagrams, you should remove white-spaces at the beginning of the check function. This will make you exit early when comparing the length despite having a potential anagram. \$\endgroup\$
    – Yousend
    Nov 7 '16 at 19:31
  • \$\begingroup\$ @thepace fair enough :) \$\endgroup\$
    – Adam J
    Nov 8 '16 at 9:49
2
\$\begingroup\$

I noticed a few different problems with your code. One small problem is you break if the lengths are not the same, but

if(count==l1 && count==l2){
        return true;
}

still checks if they both equal. One of those can be removed as it will always be true.

Another problem I have found is that if you put the break in the loops to check for more than one occurrence of a character, but if you hand trace it, it is not actually doing this.

Let's go over the loops.

You are taking one character from c1 and checking it against all characters from c2. If they match, you add one to count and break out of the c2 loop and get the next char of c1. Then you start over.

It sounds like a good plan, except that you start at the beginning of c2 again. So if c1 has multiple characters, it only recognizes the first character in c2 as matching. This will give you problems later on. Changing your input to "aabcd" "acgdb" will fool your logic.

I did it a different way, utilizing a HashMapand a ternary operator. Using a HashMap like this will help you in the long run, as it maps a char to an int, in this case one character and the amount of them. Doing this for each input will give you two maps, either identical or not.

public static void main(String[]args){
    //Diff lengths = false
    System.out.println(check("acd", "bacd"));
    //Same letters, mixed = true
    System.out.println(check("abcd", "bacd"));
    //Same string = true
    System.out.println(check("abcd", "abcd"));
    //Diff letters = false
    System.out.println(check("abcd", "gacd"));
    //Same characters = true
    System.out.println(check("abcd123$", "1b2a3c$d"));
    //Multiple occurances of a letter = true
    System.out.println(check("aaacddbg", "acadadgb"));
}

public static boolean check(String c1, String c2){
    if(c1.length() != c2.length()){
        return false;
    }

    char[] word1 = c1.toCharArray();
    char[] word2 = c2.toCharArray();

    Map<Character, Integer> map1 = new HashMap<>();
    Map<Character, Integer> map2 = new HashMap<>();

    for(int i = 0; i < word1.length; i++){
        map1.put(word1[i], (map1.get(word1[i]) == null) ? 1 : map1.get(word1[i])+1);
    }

    for(int i = 0; i < word2.length; i++){
        map2.put(word2[i], (map2.get(word2[i]) == null) ? 1 : map2.get(word2[i])+1);
    }

    if(map1.equals(map2)){
        return true;
    }else{
        return false;
    }
}
\$\endgroup\$
1
  • \$\begingroup\$ You should consider extracting map1.get(word1[i]) and map2.get(word2[i]) in those for loops into variables for a (presumably) small performance improvement (in a situation where a string contains duplicated characters you call map#.get(word#[i]) twice for each of those characters). \$\endgroup\$ Nov 7 '16 at 17:10

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.